LeetCode Trapping Rain Water

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

class Solution {
public:
    int trap(int A[], int n) {
        if (n < 1) return 0;
        vector<int> peaks;
        vector<int> peaks_tmp;

        int last_idx = 0;

        bool increasing = true;
        for (int i=1; i<n; i++) {
            if (A[i] < A[last_idx]) {
                if (increasing) {
                    peaks.push_back(last_idx);
                }
                increasing = false;
            } else {
                increasing = true;
            }
            last_idx = i;
        }
        if (increasing) peaks.push_back(n - 1);

        if (peaks.size() < 2) return 0;
        
        bool updated = true;

        while (updated) {
            updated = false;
            peaks_tmp.clear();
            peaks_tmp.push_back(peaks[0]);
            peaks_tmp.push_back(peaks[1]);
            for (int i=2; i<peaks.size(); i++) {
                int tlen = peaks_tmp.size();
                int ai = peaks_tmp[tlen - 2];
                int bi = peaks_tmp[tlen - 1];
                int ci = peaks[i];

                if (A[ai] >= A[bi] && A[ci] >= A[bi]) {
                    peaks_tmp[tlen - 1] = ci;
                    updated = true;
                } else {
                    peaks_tmp.push_back(ci);
                }
            }
            swap(peaks, peaks_tmp);
        }

        int rain = 0;

        for (int i=1; i<peaks.size(); i++) {
            int left = peaks[i - 1];
            int right= peaks[i];

            int h = min(A[left], A[right]);
            int blocks = 0;
            for (int i=left + 1; i<right; i++) blocks += A[i] > h ? h : A[i];
            rain += h * (right - left - 1) - blocks;
        }
        return rain;
    }
};

先求出各个block的峰值，然后雨水肯定落在峰值block之间，对这些峰值block为界限的区间进行合并（对于序列A{4,1,3,1,5},第一个区间为A(0,2)，第二个区间为A(2,4)，由于A[4] > A[2] 且 A[0] > A[2]所以可以合并为区间A(0, 4)），直到不能继续合并，最终计算这些block区间所能积累的水量。

再稍稍改进一下，合并过程在求峰值时同时进行，额外数组减少到一个

class Solution {
public:
        int trap(int A[], int n) {
        if (n < 1) return 0;
        vector<int> peaks;

        int last_idx = 0;

        bool increasing = true;
        for (int i=1; i<n; i++) {
            if (A[i] < A[last_idx]) {
                if (increasing) {
                    peaks.push_back(last_idx);
                    compact(A, peaks);
                }
                increasing = false;
            } else {
                increasing = true;
            }
            last_idx = i;
        }
        
        if (increasing) peaks.push_back(n - 1);
        compact(A, peaks);
        
        if (peaks.size() < 2) return 0;

        int rain = 0;

        for (int i=1; i<peaks.size(); i++) {
            int left = peaks[i - 1];
            int right= peaks[i];

            int h = min(A[left], A[right]);
            int blocks = 0;
            for (int i=left + 1; i<right; i++) blocks += A[i] > h ? h : A[i];
            rain += h * (right - left - 1) - blocks;
        }
        return rain;
    }

    void compact(int A[], vector<int> &peaks) {
        int len = peaks.size();
        if (len < 3) return;
        bool updated = true;
        while (updated && (len = peaks.size()) >= 3) {
            updated = false;
            int ai = peaks[len - 3];
            int bi = peaks[len - 2];
            int ci = peaks[len - 1];
            if (A[ai] >= A[bi] && A[ci] >= A[bi] ) {
                peaks[len - 2] = ci;
                peaks.pop_back();
                updated = true;
            }
        }
    }
};

另外一种简洁方法参见：http://www.cnblogs.com/zhuli19901106/p/3542216.html，如下

class Solution {
public:
    int trap(int A[], int n) {
        if (n < 2) return 0;
        vector<int> lmax(n, 0);
        vector<int> rmax(n, 0);
        
        int m = A[n-1];
        for (int i=n-2; i >= 0; i--) {
            if (A[i] > m) m = A[i];
            rmax[i] = m;
        }
        
        m = A[0];
        for (int i=1; i<n; i++) {
            if (A[i] > m) m = A[i];
            lmax[i] = m;
        }

        int rain = 0;
        for (int i=0; i<n; i++) {
            int h = min(lmax[i], rmax[i]);
            int v = h - A[i];
            rain += v < 0 ? 0 : v;
            
        }
        return rain;
    }
};