谁有trapping rain water的code? - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

谁有trapping rain water的code?

谁有trapping rain water的code?# JobHunting - 待字闺中

M*e2012-10-10 07:10

1 楼

想知道怎么做的。
谢谢

H*s2012-10-10 07:10

2 楼

记得在哪里看过，只用从左到右扫描一遍，每次都把当前的bar向左所能trap的容量记
下。
关键是要用一个stack来记录已处理过的bars,没时间写代码了，你可以自己试着写。

w*o2012-10-10 07:10

3 楼

这解法是O(n),空间是O(1):
大概的意思就是用左右两个指针，比较两个指针所指的值，从小的那个往中间移，移的
过程中要么增加maxL（或者maxR），要么tap water。直道两个指针相遇，其实两个相
遇在最大值。
if (bars == null || bars.length <= 2)
return 0;
int area = 0;
int l = 1, r = bars.length - 2;
int maxL = bars[0], maxR = bars[bars.length - 1];
while(l <= r)
{
if (maxL <= maxR)
{
if (bars[l] < maxL)
area += maxL - bars[l];
else
maxL = bars[l];
l++;
}
else
{
if (bars[r] < maxR)
area += maxR - bars[r];
else
maxR = bars[r];
r--;
}
}
return area;

M*e2012-10-10 07:10

4 楼

thanks

【在 w***o 的大作中提到】

: 这解法是O(n),空间是O(1):
: 大概的意思就是用左右两个指针，比较两个指针所指的值，从小的那个往中间移，移的
: 过程中要么增加maxL（或者maxR），要么tap water。直道两个指针相遇，其实两个相
: 遇在最大值。
: if (bars == null || bars.length <= 2)
: return 0;
: int area = 0;
: int l = 1, r = bars.length - 2;
: int maxL = bars[0], maxR = bars[bars.length - 1];
: while(l <= r)

H*s2012-10-10 07:10

5 楼

这个解法更简洁而且空间是O(1), wasco还是牛啊！

【在 w***o 的大作中提到】