06
05/2015
[LeetCode] Trapping Rain Water
Trapping Rain Water
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!
解题思路：
1、我的办法：两边夹的思想，若左边小于右边，则移动左边的指针，否则移动右边的指针。同时，若移动的指针小于上一个最小高度，则容量减去该移动指针此时所指的高度。若移动的指针和未移动的指针都大于此前最小高度，则加上超出的部分。说的不明白，代码比较好理解：
class Solution {
public:
int trap(vector<int>& height) {
int len = height.size();
if (len<3){
return 0;
}
int start = 0, end = len - 1;
int result = 0, minH = 0;
minH = min(height[start], height[end]);
result = minH * (end - start - 1);
while (start<end - 1){
if (height[start]<height[end]){
start++;
result = result - min(minH, height[start]);
}
else{
end--;
result = result - min(minH, height[end]);
}
if (height[start]>minH && height[end]>minH){
result += min(height[start] - minH, height[end] - minH) * (end - start - 1); //加上超出的部分
minH = min(height[start], height[end]);
}
}
return result;
}
};2、网上另外一个比较好的办法是左右两边扫的办法。记录每个数左边和右边最大的数。左边最大与右边最大构成一个容器，减去本身的空间，这相当于这个位置上的台阶贡献了容量。
class Solution {
public:
int trap(vector<int>& height) {
int len = height.size();
if (len<3){
return 0;
}
int maxL[len], maxR[len];
int maxH = height[0];
maxL[0] = 0;
for(int i=1; i<len; i++){
maxL[i] = maxH;
maxH = max(maxH, height[i]);
}
maxH = height[len-1];
maxR[len-1]=0;
int result=0;
for(int i=len-2; i>=0; i--){
maxR[i]=maxH;
maxH = max(maxH, height[i]);
result +=max(0, min(maxL[i], maxR[i]) - height[i]);
}
return result;
}
};转载请注明：康瑞部落 » [LeetCode] Trapping Rain Water
0 条评论