42. 接雨水
题目描述
思路分析
模拟
每个位置存水量,取决于左边最大高度,右边最大高度,和自己的高度。
代码实现
class Solution {
public:
int trap(vector<int>& height) {
if(height.size()==0) return 0;
int n=height.size(),res=0;
vector<int> left(n+1),right(n+1);
left[0]=height[0],right[n-1]=height[n-1];
for(int i=1;i<n;i++){
left[i]=max(left[i-1],height[i]);
}
for(int i=n-2;i>=0;i--){
right[i]=max(right[i+1],height[i]);
}
for(int i=0;i<n;i++){
res+=min(left[i],right[i])-height[i];
}
return res;
}
};