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 p_w_picpath!
解法:
对数组,至少有一个最高点,
两头向中间扫描,左边找到局部最高点leftmaxLocal,当当前高度比leftmaxLocal小,则area+=(leftmaxLocal-curheight),否则更新leftmaxLocal;同理右边也是这样。
int trap(vector<int>& height) {
int size=height.size();
if(size<3)
return 0;
int left=0,right=size-1;
int lhm=0,rhm=0;
int lhc=0,rhc=0;
int area=0;
while(left<=right){
lhc=height[left];
rhc=height[right];
if(lhc<rhc){
if(lhm>lhc)
area+=(lhm-lhc);
else
lhm=lhc;
left++;
}
else{
if(rhm>height[right]){
area+=(rhm-height[right]);
}
else
rhm=height[right];
right--;
}
}
return area;
}