正文
刷题42. Trapping Rain Water
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
一、题目说明
题目是42. Trapping Rain Water，翻译起来就是“接雨水”。给n个非负正数代表高度，每个正数宽度为1，让计算能多少雨水。题目难度是Hard
二、我的解法
这个题目是找“坑”，然后计算里面可以存的“雨”。总共提交了5次，前面几次都是边界错误。
代码如下：
#include<iostream>
#include<vector>
using namespace std;
class Solution{
public:
int trap(vector<int>& height){
if(height.size()<1) return 0;
int len = height.size();
int sum = 0,area=0,h;
bool lflag = false,rflag = false;
int left=0,leftStart,right,rightEnd=len-1,mid;
while(left<rightEnd){
//从左边开始找第1个高度
leftStart = left;
while(leftStart<len-1 && height[leftStart]<=height[leftStart+1]){
leftStart++;
}
left = leftStart;
//从右边开始找第1个高度
right = rightEnd;
while(right>left && height[right]<=height[right-1]){
right--;
}
rightEnd = right;
if(height[rightEnd]<=height[left]){
right = rightEnd;
//降
while(right>left && (height[right]<=height[rightEnd])){
right--;
}
//升
while(right>left && (height[right]<height[right-1])){
right--;
}
h = height[right]<height[rightEnd] ? height[right]: height[rightEnd];
area = 0;
for(int t=right+1;t<rightEnd;t++){
if(h>height[t]){
area = area + (h-height[t]);
}
}
sum += area;
rightEnd = right;
}else{
leftStart = left;
//降
while(left<rightEnd && (height[left]<=height[leftStart])){
left++;
}
//升
while(left<rightEnd && (height[left]<height[left-1])){
left++;
}
h = height[left]<height[leftStart] ? height[left]: height[leftStart];
area = 0;
for(int t=leftStart+1;t<left;t++){
if(h>height[t]){
area = area + (h-height[t]);
}
}
sum += area;
leftStart = left;
}
}
return sum;
}
};
int main(){
Solution s;
vector<int> r;
r = {0,1,0,2,1,0,1,3,2,1,2,1};
cout<<s.trap(r)<<":"<<(6==s.trap(r))<<"\n";
r = {5,4,1,2};
cout<<s.trap(r)<<":"<<(1==s.trap(r))<<"\n";
r = {5,2,1,2,1,5};
cout<<s.trap(r)<<":"<<(14==s.trap(r))<<"\n";
r = {5,5,1,7,1,1,5,2,7,6};
cout<<s.trap(r)<<":"<<(23==s.trap(r))<<"\n";
r = {6,4,2,0,3,2,0,3,1,4,5,3,2,7,5,3,0,1,2,1,3,4,6,8,1,3};
cout<<s.trap(r)<<":"<<(83==s.trap(r))<<"\n";
return 0;
}
性能如下：
Runtime: 8 ms, faster than 61.40% of C++ online submissions for Trapping Rain Water.
Memory Usage: 9.1 MB, less than 91.14% of C++ online submissions for Trapping Rain Water.
三、优化措施
代码虽然正确，但看起来很难过！多番寻找，相对优雅的代码如下：
class Solution{
public:
//left、right
int trap(vector<int>& height) {
int n = height.size();
int lhigh = 0, rhigh = n-1;
int diff = 0;
// scan from left to right
for(int i = lhigh; i<n; i++)
{
if (height[i] < height[lhigh]) continue;
for (int j = lhigh+1; j<i; j++) diff += height[lhigh]-height[j];
lhigh = i;
}
// scan from right to left
for (int i = rhigh; i>=lhigh; i--)
{
if (height[i] < height[rhigh]) continue;
for (int j = i+1; j<rhigh; j++) diff += height[rhigh]-height[j];
rhigh = i;
}
return diff;
}
};
性能虽然差点，但可读性好多了。
Runtime: 12 ms, faster than 17.25% of C++ online submissions for Trapping Rain Water.
Memory Usage: 9 MB, less than 94.94% of C++ online submissions for Trapping Rain Water.
