首页 > 代码库 > [leetcode] Trapping Rain Water
[leetcode] 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.
图1
思路：1. 我通过观察测试用例[0,1,0,2,1,0,1,3,2,1,2,1]和上面示意图，发现蓄水的地方存在于子序列[1,0,2],[2,1,0,1,3],[2,1,2]的地方，这样的子序列有个共同特点就是两边的数据大（想象成河的堤），中间的数据小（想象成河底的礁石或凸起）。
2. 通过1中的想法，我得到初步的解决方案： 首先从图中可以直观的看出，要想能蓄水，序列中至少需要3个数（两边高，中间低）；然后设置两个指针，指针i初始化为指向序列的第一个元素，指针j初始化为i+1，设序列（数组）名为num，从j开始，我期望找到第一个比num[i]大的数，如果j=i+1，那么就是不能蓄水的，如序列起始位置的[0,1],这时我可以将i加1，这样我就能找到第一个子序列[1,0,2]，其中i指向1下标为1，j指向2，下标为3，河宽=j-i-1=3-1-1=1，河高为1，蓄水量为河宽*河高=1*1=1. 蓄完水怎么办，从图
1中可以直观地看出，将i赋值为j，将j赋值为j+1，再重复上述步骤。我的思路可以概括为找河堤，然后蓄水，那么问题来了，我们找到的第一个序列[1,0,2]中是没有礁石的，换句话说，两个较大的数（河堤）中间夹的都是0（河底是平的），这样就可以按照河宽*河高的方法计算蓄水量，那么像第二个序列[2,1,0,1,3]，我从数值2为起点，找到了第一个比它大的数3作为另一个堤，这时的i（2的下标）是3，j（3的下标）是7，在不考虑礁石（num[i]和num[j]之间的非零值）的情况下，蓄水量应该是（7-3-1）*2=6，那么礁石所占据的面积怎么减去呢，稍微观察一下发现num[i]和num[j]之间的数的和就是礁石的总面积，所以考虑子序列[2,1,0,1,3]的蓄水量就是6-（1+0+1）=4.
3. 到这里问题貌似解决了，但是接着出现了这样一个问题，对于num[i],我找第一个比num[i]大的数作为另一半河堤，上述两个序列都是能找到的情况，如果接着第2步，这时我需要将i赋值为值3的下标也就是7，这时我往前找找不到比num[i]大的值怎么办，将i++可以解决图1中的问题，于是，我写成了下列代码：
class Solution {public: int trap(int A[], int n) { if(n<=2) return 0; int i=0,j,temp; int result = 0; while(i<n-2) { j=i+1; temp=0; while(A[j]<A[i]&&j<n) { temp += A[j]; j++; } if(j==i+1||j==n) //the next is bigger or no num bigger than A[i] { i++; }else{ int length = j-i-1; int height = min(A[i],A[j]); int area = height*length; area -= temp; result += area; i=j; } } return result; }};
4. 按照第3步中，我如果往前找，找不到比当前大的值，我的做法是直接丢弃当前值，但这样是有问题的，因为要蓄水，只要有凹槽就行（两边大，中间小），不一定要找到比当前值大的值，比如序列[4,2,3],那么当j==n的时候（没有找到比num[i]大的值），取min(num[n-1],num[i])作为河高，（j-i-1）作为河宽，减去中间的礁石（temp）就可以呢？显然不是，如果序列是[4,2,3,1]这样做就不行，最后我想出的办法是削堤，也就是当无法找到比num[i]大的值的时候，我就将num[i]减小至剩下的数中最大的值，如[4,2,3,1]，我就将4变为3，问题得到解决。输出如下代码：
class Solution {public: int trap(int A[], int n) { if(n<=2) return 0; int i=0,j,temp; int result = 0; while(i<n-2) { j=i+1; temp=0; int max = A[j]; while(A[j]<A[i]&&j<n) { if(A[j]>max) max = A[j]; temp += A[j]; j++; } if(j==i+1) //the next is bigger or no num bigger than A[i] { i++; }else if(j==n){ A[i]=max; // cut down A[i] }else{ int length = j-i-1; int height = A[i]; int area = height*length; area -= temp; result += area; i=j; } } return result; }};
[leetcode] Trapping Rain Water