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.

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!

Tags: Array Stack Two Pointers

第一次自己的算法用了奇技淫巧，勉强过关，但代码修修补补的，不够简洁。具体思路是模仿那个最大直方图矩形面积的思路，维护一个栈。

class Solution {
public:
    int trap(int A[], int n) {
        stack<int> s;
        int lastLevel = 0;
        int sum = 0;
        int isIncreasing = true;
        if(n <= 2){
            return 0;
        }
        for(int i = 1; i < n ; i++){
            if(A[i] >= A[i - 1] && s.empty() == true){//increasing
                isIncreasing = true;
            }
            else if(A[i] < A[i - 1]){
                if(isIncreasing == true){//i - 1 is the peek
                    s.push(i - 1);
                }
                s.push(i);
                isIncreasing = false;
            }
            else{
                while(s.empty() == false && A[s.top()] <= A[i]){
                    int left = s.top();
                    s.pop();
                    sum += (i - left - 1) * (A[left] - lastLevel);
                    lastLevel = A[left];
                }
                if(s.empty() == true){
                    lastLevel = 0;
                    isIncreasing = true;
                }
                else{
                    sum += (i - s.top() - 1) * (A[i] - lastLevel);
                    lastLevel = A[i];
                    s.push(i);
                }
            }
        }
        return sum;
    }
};

其实有更简洁的方法。

A[i]该柱子的存水量取决于它左边最高的柱子的值与右面最高柱子的值的最小值，即min(leftmost[i],rightmost[i]) – A[i]。所以可以这样来解：

先从左到右遍历，构建leftMost数组；再从右到左遍历，构建rightMost数组；再从左到右遍历，求出每个柱子的蓄水值，结束。o(n)的时间与空间复杂度。

class Solution {
public:
    int trap(int A[], int n) {
        if(n < 3){
            return 0;
        }
        int leftMost[n] = {0};
        int rightMost[n] = {0};
        int sum = 0;
        
        leftMost[0] = A[0];
        rightMost[n - 1] = A[n - 1];
        for(int i = 1; i < n; i++){
            leftMost[i] = max(leftMost[i - 1], A[i]);
            rightMost[n - i - 1] = max(rightMost[n - i], A[n - i - 1]);
        }
        for(int i = 0; i < n; i++){
            sum += abs(min(leftMost[i], rightMost[i]) - A[i]);
        }
        return sum;
    }
};

其实还有更简单的方法：

用双指针left和right，由两边向中间遍历。维护一个secHight第二高的变量。

代码待补充