leetcode-42. 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. 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 Marcosfor contributing this image! Example: Input: [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6

給定 n 個非負整數表示每個寬度為 1 的柱子的高度圖，計算按此排列的柱子，下雨之後能接多少雨水。 上面是由數組 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度圖，在這種情況下，可以接 6 個機關的雨水（藍色部分表示雨水）。 感謝 Marcos 貢獻此圖。 示例: 輸入: [0,1,0,2,1,0,1,3,2,1,2,1] 輸出: 6

思路：這道題目 類似于直方圖中的 最大矩形和盛水最多的容器。第一種方法就是，i和j分别從前往後和從後往前周遊直到i>=j，看他們對應的 值哪個小，若height[i]<=height[j]，那就從左往右如果遇到的 高度小于目前的 高度，加上height[i]與目前高度的差；若height[i]>height[j]，那就從右往左如果遇到高度小于目前高度，則res加上height[j]與擋圈高度的差。最終res就是雨水容量。比如題目中從前往後height[2]<height[1],那res+=1,(注釋height[1]-height[2]),接着從後往前height[9]<height[10],res+=1,(注釋height[10]-height[9]),接着從前往後height[4]<height[3],res+=1,（注釋，height[3]-height[4]）,接着繼續Height[5]<height[3],res+=2,（注釋，height[3]-height[5]）,接着繼續往後height[6]<height[3],res+=1，（注釋，height[3]-height[6]）。下面是第一種代碼實作

第二種方法是使用DP。我們維護一個一維的dp數組，這個DP算法需要周遊兩遍數組，第一遍周遊dp[i]中存入i位置左邊的最大值，然後開始第二遍周遊數組，第二次周遊時找右邊最大值，然後和左邊最大值比較取其中的較小值，然後跟目前值A[i]相比，如果大于目前值，則将內插補點存入結果

class Solution {
public:
    int trap(vector<int>& height) {
        int res = 0, mx = 0, n = height.size();
        vector<int> dp(n, 0);
        for (int i = 0; i < n; ++i) {
            dp[i] = mx;
            mx = max(mx, height[i]);
        }
        mx = 0;
        for (int i = n - 1; i >= 0; --i) {
            dp[i] = min(dp[i], mx);
            mx = max(mx, height[i]);
            if (dp[i] > height[i]) res += dp[i] - height[i];
        }
        return res;
    }
};
           

第三種是用棧。

二三種方法參考：http://www.cnblogs.com/grandyang/p/4402392.html

class Solution {
public:
    int trap(vector<int>& height) {
        int res=0,i=0,j=height.size()-1;
        while(i<j)
        {
            int small=min(height[i],height[j]);
            if(small==height[i])
            {
                ++i;
                while(i<j && height[i]<small)
                    res += small - height[i++];
            }else
            {
                --j;
                while(i<j && height[j]<small)
                    res +=small - height[j--];
            }
        }return res;
    }
};