刷题42. Trapping Rain Water _刷题

从来好事天生俭，自古瓜儿苦后甜。这篇文章主要讲述刷题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))< < " " ; r = {5,4,1,2}; cout< < s.trap(r)< < " :" < < (1==s.trap(r))< < " " ; r = {5,2,1,2,1,5}; cout< < s.trap(r)< < " :" < < (14==s.trap(r))< < " " ; r = {5,5,1,7,1,1,5,2,7,6}; cout< < s.trap(r)< < " :" < < (23==s.trap(r))< < " " ; 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))< < " " ; 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; } };

【刷题42. Trapping Rain Water】性能虽然差点，但可读性好多了。

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.