[leetcode] Trapping Rain Water

浏览数：26 / 时间：2015年06月11日

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;
    }
};