M******e
发帖数: 103 | | H****s
发帖数: 247 | 2 记得在哪里看过，只用从左到右扫描一遍，每次都把当前的bar向左所能trap的容量记
下。
关键是要用一个stack来记录已处理过的bars,没时间写代码了，你可以自己试着写。 | w***o
发帖数: 109 | 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******e
发帖数: 103 | 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****s
发帖数: 247 | 5 这个解法更简洁而且空间是O(1), wasco还是牛啊！
【在 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)
|
|
