给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。 感谢 Marcos 贡献此图。
示例:
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6
class Solution {
public int trap(int[] height) {
int left=0,right=1;
int length=height.length;
int total=0;
int maxPos=-1;
while(left<length){
maxPos=right;
while(right<length&&height[right]<height[left]){
if(height[right]>height[maxPos])
maxPos=right;
right++;
}
if(right==length){
if(maxPos==length){
total+=height[left];
break;
}
total+=(height[left]-height[maxPos]);
total+=(height[maxPos]*(maxPos-left));
left=maxPos;
right=left+1;
continue;
}else{
total+=(height[left]*(right-left));
left=right;
right++;
}
}
for(int i=0;i<length;i++)
total-=height[i];
return total;
}
}