logo
Redian新闻
>未名空间
>JobHunting - 待字闺中
>
请教一道题
avatar
请教一道题# JobHunting - 待字闺中
m*a
1 楼
一个height的二维数组，height[n][m]，n,m 分别代表一块陆地的长和宽，height数组
里面的value代表陆地上的每个点的高度，问如果下了很大一场雨（足够多水），问这
块陆地最多能容纳多少水？当然陆地的四个边上面是不能储水的。
请问这题有什么好的解法么？谢谢！
avatar
w*8
2 楼
可以先考虑一维情况，感觉二维和一维的解法思路类似，从外圈开始，往里走一个点一
个点的计算存水量。
avatar
m*a
3 楼
各位大牛路过，还请不惜赐教。
avatar
h*0
4 楼
......lz 能分清什么是3维和2维数组么
avatar
V*a
6 楼
lintcode上曾经有原题（trapping water II），后来不知道为什么被拿掉了。
大致解法（可能细节有误）是用根据水位建一个heap，初始化是从区域的边界开始，每
次pop，然后update its 4 neighbors，放入heap，如此循环。
avatar
b*r
7 楼
对每个点，按X方向求最大值，再按Y方向求最大值。然后取最小值。O(N^3)。应该可以
优化。
其实就是1唯到2唯的扩展。

【在 V***a 的大作中提到】
: lintcode上曾经有原题（trapping water II），后来不知道为什么被拿掉了。
: 大致解法（可能细节有误）是用根据水位建一个heap，初始化是从区域的边界开始，每
: 次pop，然后update its 4 neighbors，放入heap，如此循环。
avatar
b*c
8 楼
leetcode上有道题计算直方图里的最大矩形：https://siddontang.gitbooks.io/
leetcode-solution/content/array/largest_rectangle_in_histogram.html
是不是这个题的变形？
avatar
b*r
9 楼
看楼上VYCMa大牛的回复，是max trapping water的扩展

【在 b*****c 的大作中提到】
: leetcode上有道题计算直方图里的最大矩形：https://siddontang.gitbooks.io/
: leetcode-solution/content/array/largest_rectangle_in_histogram.html
: 是不是这个题的变形？
相关阅读
王垠：对中国人的信心 (转载)有人需要改简历吗？希望是U家最后一次事故这三种工作怎么选择？索南码工偷代码遭殃了 (转载)如何在职场上做到不慌张？湾区startup招人如果python command line positional arguments 里有些是运算quip这家公司怎么样？硅谷华工人人pip不是梦 (转载)请问有人知道大公司onsite interview的细节流程吗IBM 又犯病了Re: 《摔跤》不如《盲井》 (转载)女码农Amazon过了社招onsite求match湾区&西雅图的组三藩市招一个Mobile Developer苹果股东再次否决加强员工多样化提案 (转载)大仇得报？王垠说的没错 (转载)找工作求建议求收留大龄女子早点找个结婚对象稳固家庭再搞事业?(转载)
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章，不代表同意其说法或描述，仅为提供更多信息，也不构成任何建议。文章信息的合法性及真实性由其作者负责，与Redian.news及其运营公司无关。欢迎投稿，如发现稿件侵权，或作者不愿在本网发表文章，请版权拥有者通知本网处理。