LeetCode 42. Trapping Rain Water

[Woodyiiiiiii]

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.

Example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

---

一开始我的想法是对每个水柱向右遍历寻找符合条件的水柱，然后再跳到水柱边界，循环数组直至结尾。然而这就衍生出很多复杂的情况。所以简单的思路是对每一个单位的水柱进行计算，不要计算单位水柱形成的整体水柱的整体体积，要把它分隔成一个个单位水柱。

解法一:
对每个水柱计算其左边最高的高度和右边最高的高度，对两高度值取最小的，如果结果比当前高度还高，则说明这里可以形成一个单位水柱，计算结果。遍历整个数组即可。

我们用类似DP的思想，维护一个一维动态DP数组，先从左到右遍历求得每个元素最左边的最高高度(最左边界为0)，然后再从右往左求得每个元素最右边的最高高度(最右边界为0)，再计算符合条件的单位水柱体积，累加和为整体水柱体积。

class Solution {
    public int trap(int[] height) {
        int max = 0, i, res = 0, n = height.length;
        int[] dp = new int[n];
        for (i = 0; i < n; ++i) {
            dp[i] = max;
            max = Math.max(height[i], max);
        }
        max = 0;
        for (i = n - 1; i >= 0; --i) {
            dp[i] = Math.min(dp[i], max);
            max = Math.max(height[i], max);
            if (dp[i] > height[i]) {
                res += dp[i] - height[i];
            }
        }
        return res;
    }
}

其实这种做法是可以不用维护一个一维数组空间的，当然需要多消耗时间，增加了时间复杂度，从O(n)到O(n^2)，但思路清晰了些：

class Solution {
    public int trap(int[] height) {
        int max = 0, i, j, res = 0, n = height.length, leftMax, rightMax;
        for (i = 0; i < n; ++i) {
            leftMax = 0;
            rightMax = 0;
            for (j = 0; j < i; ++j) {
                leftMax = Math.max(leftMax, height[j]);
            }
            for (j = n - 1; j > i; --j) {
                rightMax = Math.max(rightMax, height[j]);
            }
            max = Math.min(leftMax, rightMax);
            if (max > height[i]) {
                res += max - height[i];
            }
        }
        return res;
    }
}

解法二:
我们可以继续优化解法一的算法——解法一需要分两次遍历数组，其中还需要将第一次遍历的结果储存起来，那么我们可以尝试只需要遍历一次数组，不需要储存数据的解法，也就是 双指针(Two pointers) 的解法。

左边指针从左往右，右边指针从右往左，直至两者碰撞。比较两个指针所指高度哪个较小，就移动哪个指针，直到高度大于它原来高度的位置或者与另一个指针碰撞。移动过程计算单位水柱高度。

这个过程可以类比于解法一，其实比较大小就是找到了元素的左边和右边的最小值。比较难懂，细细思考一下就可以了。

class Solution {
    public int trap(int[] height) {
        int l = 0, r = height.length - 1, res = 0;
        while (l < r) {
            int min = Math.min(height[l], height[r]);
            if (height[l] == min) {
                ++l;
                while (l < r && height[l] < min) {
                    res += (min - height[l++]);
                }
            }else {
                --r;
                while (l < r && height[r] < min) {
                    res += (min - height[r--]);
                }
            }
        }
        return res;
    }
}

解法三:
参考相似题目 84. Largest Rectangle in Histogram，可以使用栈的方法找到当前元素左边界的最高高度。换句话说，先抛出栈顶元素(元素是横坐标)，如果栈为空，说明不能形成水柱，否则此时的栈顶为左边界坐标，而当前坐标为右边界，取两个边界高度的最小值，再计算左右边界的宽度，求得水柱体积。也就是说，这是计算整体水柱体积的方法，但是使用了栈巧妙地存储了左边界高度。

此解法使用了单调栈数据结构，即保证栈底到栈顶的元素是按照从大到小排序的。

class Solution {
    public int trap(int[] height) {
        Stack<Integer> s = new Stack<>();
        int i = 0, n = height.length, res = 0;
        while (i < n) {
            if (s.isEmpty() || height[i] <= height[s.peek()]) {
                s.push(i++);
            }else {
                int t = s.pop();
                if (s.isEmpty()) continue;
                res += (Math.min(height[i], height[s.peek()]) - height[t])
                        * (i - s.peek() - 1);
            }
        }
        return res;
    }
}

---

相似题目：

• 84. Largest Rectangle in Histogram

参考资料：

• https://leetcode.com/problems/trapping-rain-water/
• [LeetCode] 42. Trapping Rain Water grandyang/leetcode#42