学步园

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!

方法一：收集雨水

左边右边中短者为堤坝。比堤坝更短者可蓄一定的水。逐步收集这些水量。比当前堤坝更高者，将成为新堤坝。

此算法在leetcode上实际执行时间为10ms。

class Solution {
public:
    int trap(int A[], int n) {
        int low = 0, high = n-1;
        int rain = 0, bar = 0;

        while (low < high) {
                if (A[low] < A[high]) {
                        if (bar < A[low])
                                bar = A[low];
                        else
                                rain += bar-A[low];

                        ++low;
                }
                else {
                        if (bar < A[high])
                                bar = A[high];
                        else
                                rain += bar-A[high];

                        --high;
                }
        }

        return rain;
    }
};

方法二，假定都是雨水，再逐步刨出那些堤坝占据的水量。

此算法在leetcode 上实际执行时间为13ms。比上面慢点，可能是因为用到了乘法。

class Solution {
public:
    int trap(int A[], int n) {
        int low = 0, high = n-1;
        int bar = 0, rain = 0;

        while (low < high) {
                const int newbar = min(A[low], A[high]);
                if (newbar > bar) {
                        rain += (newbar-bar) * (high-low);
                        bar = newbar; 
                }

                if (A[low] < A[high]) {
                        rain -= min(bar, A[low]);
                        ++low;
                }
                else {
                        rain -= min(bar, A[high]);
                        --high;
                }
        }

        return rain;
    }
};