Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
For example,
Given [0,1,0,2,1,0,1,3,2,1,2,1]
, return 6
.
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!
注意对每根柱子能盛的水并不是自身能决定的,而是取决于其左右两边的柱子。
先记录最高的柱子maxHeight,把数组一分为二,分别计算最高柱子左右两边的盛水量。
对于最高柱子左边的部分,
从首端开始扫描,并使用leftHeight记录已扫描部分的中得最高柱子。
如果leftHeight > curHeight,说明当前柱子能盛水,当前柱子所盛水的容量为leftHeight-curHeight
如果leftHeight<= curHeight,说明当前柱子不能盛水,则更新leftHeight = curHeight
对于最高柱子右边的部分,从末端开始倒序扫描,求右半部分的水,即可
class Solution {
public:
int trap(int A[], int n) {
int maxHeightIndex = ;
for(int i = ; i < n; ++ i){
if(A[i] > A[maxHeightIndex]) maxHeightIndex = i;
}
int leftHeight = ,res = ;
for(int i = ; i < maxHeightIndex;++ i){
if(leftHeight > A[i]) res+=leftHeight-A[i];
else leftHeight = A[i];
}
int rightHeight = ;
for(int i = n-; i>maxHeightIndex; --i){
if(rightHeight > A[i]) res+=rightHeight-A[i];
else rightHeight = A[i];
}
return res;
}
};