42. Trapping Rain Water (Hard)

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.

Solution 1: find local min

这道收集雨水的题跟之前的那道 Largest Rectangle in Histogram 直方图中最大的矩形 有些类似，但是又不太一样，我最先想到的方法有些复杂，但是也能通过OJ，想法是遍历数组，找到局部最小值，方法是如果当前值大于或等于前一个值，或者当前值大于后一个值则跳过，找到了局部最小值后，然后我们首先向左找到左边的最大值，再找右边的最大值，找右边最大值时要注意当其大于左边最大时时就停止寻找了，然后算出从左边最大值到右边最大值之间能装的水量，之后从右边最大值的位置开始继续找局部最小值，以此类推直到遍历完整个数组，代码如下：

int trap(vector<int>& height) {
    int n = height.size(), left = 0, right = 0, level = 0, res = 0;
    for (int i = 1; i < n-1; ++i) {
        // not local min, move to next entry
        if (height[i] >= height[i-1] || height[i] > height[i+1]) continue;
        // find left and right max of current local min
        for (left = i-1; left > 0; --left) {
            if (height[left] >= height[left-1]) break;
        }
        // stop when right max is taller than left max
        right = i + 1;
        for (int j = i + 1; j < n; ++j) {
            if (height[j] >= height[right]) {
                right = j;
                if (height[right] >= height[left]) break;
            }
        }

        level = min(height[left], height[right]);

        for (int j = left + 1; j < right; ++j) {
            if (level-height[j] > 0) res += (level-height[j]);
        }
        i = right;
    }
    return res;

}

Solution2: dp

O(n) = 2n

那么我们再来看另一种方法，这种方法是基于动态规划Dynamic Programming的，我们维护一个一维的dp数组，这个DP算法需要遍历两遍数组，第一遍遍历dp[i]中存入i位置左边的最大值，然后开始第二遍遍历数组，第二次遍历时找右边最大值，然后和左边最大值比较取其中的较小值，然后跟当前值A[i]相比，如果大于当前值，则将差值存入结果，代码如下：

int trap(vector<int>& height) {
    int n = height.size();
    if (n == 0) return 0;
    vector<int> left(n);
    left[0] = height[0];
    for (int i = 1; i < n; ++i) {
        left[i] = max(left[i-1], height[i]);
    }
    int right = height[n-1];
    int res = 0;
    for (int i = n-1; i >= 0; --i) {
        right = max(right, height[i]);
        res += min(left[i], right)-height[i];
    }
    return res;
}

Solution3: two pointer

用两个指针从两端往中间扫，在当前窗口下，如果哪一侧的高度是小的，那么从这里开始继续扫，如果比它还小的，肯定装水的瓶颈就是它了，可以把装水量加入结果，如果遇到比它大的，立即停止，重新判断左右窗口的大小情况，重复上面的步骤。这里能作为停下来判断的窗口，说明肯定比前面的大了，所以目前肯定装不了水（不然前面会直接扫过去）。这样当左右窗口相遇时，就可以结束了，因为每个元素的装水量都已经记录过了。代码如下：

O(n) = n

int trap(vector<int>& height) {
    int n = height.size();
    int res = 0, left = 0, right = n-1;
    while (left < right) {
        int level = min(height[left], height[right]);
        if (level == height[left]) {
            ++left;
            while (left < right && height[left] < level) {
                res += level-height[left];
                ++left;
            }
        } else {
            --right;
            while (left < right && height[right] < level) {
                res += level - height[right];
                --right;
            }
        }
    }
    return res;
}
// simpler way
int trap(vector<int>& height) {
    int l = 0, r = height.size()-1, level = 0, water = 0;
    while (l < r) {
        int lower = height[height[l] < height[r] ? l++ : r--];
        level = max(level, lower); // level is wall
        water += level - lower;
    }
    return water;
}

Solution4: stack

Using the same method as the max-rectangle problem. Use the stack top as the bottom, second stack top as the left boundary, current as the right boundary, then accumulate the total area.

int trap(vector<int>& height) {
    int n = height.size();
    if(n < 3) return 0;

    stack<int> s; // store index
    s.push(0);
    int water = 0;

    for(int i = 1; i < n; ++i) {
        // columns in stack will be decreasing in height.
        // current column index is "i"
        if (s.empty() || height[s.top()] > height[i]) {
            // if we encounter a column lower  than the previous one, push it to stack.
            s.push(i);
        } else {
            // if we encounter a column higher than the previous one (denoted as "bottom"), start poping,
             // calculate the water trapped between column before bottom and "i"
            int bottom = height[s.top()]; s.pop();
            if (!s.empty()) {
                // rectangle size
                water += (min(height[i],height[s.top()])-bottom)*(i-s.top()-1);
            }
            --i; //stay at the same place for further merge
        }
    }
    return water;
}