Trapping Rain Water

Two Pointers, Stack, Dynamic Programming

Hard

Question

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.

Trapping Rain Water

Trapping Rain Water

Example

Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

Challenge

O(n) time and O(1) memory

O(n) time and O(n) memory is also acceptable.

Tags

Two Pointers Forward-Backward Traversal Array

Related Problems

• Medium Container With Most Water

• Hard Trapping Rain Water II

• Candy

Analysis

Reference: https://leetcode.com/articles/trapping-rain-water/

Brute Force

最直觉的想法就是对于每个bar，找到其左边和右边最大的bar height: leftMax, rightMax，再减去bar本身的高度heights[i]，就得到该处能存水的量。嵌套两重循环，每次只储存某个bar的左右最大height，因此

Time Complexity O(n^2), Space Complexity O(1)

Dynamic Programming

对于每一个bar来说，能装水的容量取决于左右两侧bar的最大值。扫描两次，一次从左向右，记录对于每一个bar来说其左侧的bar的最大高度left[i]，一次从右向左，记录每一个bar右侧bar的最大高度right[i]。第三次扫描，则对于每一个bar，计算

（1）左侧最大height和当前bar的height的差值（left[i] - heights[i]）

（2）右侧最大height和当前bar的height的差值（right[i] - heights[i]），

取（1），（2）中结果小的那个作为当前bar的蓄水量。最终求和得到总蓄水量。或者直接找到bari两侧最大height中最小的那个，再找与heights[i]的大于零的差值即可。

The water each bar can trap depends on the maximum height on its left and right. Thus scan twice - from left to right, and right to left and record the max height in each direction. The third time calculate the min difference between left/right height and current bar height. Sum the trapped water to get the final result.

简而言之：找左边最大和右边最大可以通过两个dp数组来存起来.

dpLeft[i] = Math.max(dpLeft[i - 1], height[i]); dpRight[i] = Math.max(dpRight[i + 1], height[i]);

Time: O(N), Space: O(2*N)

Two Pointers

@Grandyang: 我们来看一种只需要遍历一次即可的解法，这个算法需要left和right两个指针分别指向数组的首尾位置，从两边向中间扫描，在当前两指针确定的范围内，先比较两头找出较小值，如果较小值是left指向的值，则从左向右扫描，如果较小值是right指向的值，则从右向左扫描，若遇到的值比当较小值小，则将差值存入结果，如遇到的值大，则重新确定新的窗口范围，以此类推直至left和right指针重合。

Time: O(N), Space: O(1)

Monotonic Stack

@reeestart: 和largest rectangle in histogram一样的思路. 只不过histogram是用递增栈, 这道题是使用递减栈. stack里存的也是index.

每次出栈的时候是处理出栈的栈顶元素而非当前元素. 因为每次需要出栈的时候我们可以确定:

• height[stk.peek()] < height[stk.peek().peek()], stk.peek().peek() 就是栈顶第二大的元素.

• height[stk.peek()] < height[i]

Solution

Brute Force

class Solution {
    public int trap(int[] height) {
        if (height == null || height.length <= 2) {
            return 0;
        }
        int ans = 0;
        for (int i = 0; i < height.length; i++) {
            int leftMax = 0; 
            int rightMax = 0;
            int j = i - 1;
            int k = i + 1;
            int waterHeight = 0;
            while (j >= 0) {
                leftMax = Math.max(height[j], leftMax);
                j--;
            }
            while (k < height.length) {
                rightMax = Math.max(height[k], rightMax);
                k++;
            }
            waterHeight = Math.min(leftMax, rightMax);
            ans += Math.max(waterHeight - height[i], 0);
        }
        return ans;
    }
}

Dynamic Programming

public class Solution {
    /**
     * @param heights: an array of integers
     * @return: a integer
     */
    public int trapRainWater(int[] heights) {
        if (heights == null || heights.length < 3) {
            return 0;
        }
        int length = heights.length;

        int[] left = new int[length];
        int[] right = new int[length];

        int trapped = 0;

        // For heights[0] or heights[length - 1], the max left/right height is 0
        left[0] = 0;
        right[length - 1] = 0;

        // Keep track of the max height on the left of height[i]
        for (int i = 1; i < length; i++) {
            left[i] = Math.max(left[i - 1], heights[i - 1]);
        }

        // Keep track of the max height on the right of height[i]
        for (int j = length - 2; j >= 0; j--) {
            right[j] = Math.max(right[j + 1], heights[j + 1]);
        }

        // Calculate the total trapped water
        for (int k = 0; k < length; k++) {
            trapped += Math.max(Math.min(left[k], right[k]) - heights[k], 0);
        }

        return trapped;
    }
}

Two Pointers

class Solution {
    public int trap(int[] height) {
        if (height == null || height.length <= 2) {
            return 0;
        }
        int leftMax = 0, rightMax = 0;
        int left = 0, right = height.length - 1;
        int trapped = 0;
        while (left < right) {
            if (height[left] < height[right]) {
                if (height[left] >= leftMax) {
                    leftMax = height[left];
                } else {
                    trapped += Math.max(leftMax - height[left], 0);
                }
                left++;
            } else {
                if (height[right] >= rightMax) {
                    rightMax = height[right];
                } else {
                    trapped += Math.max(rightMax - height[right], 0);
                }
                right--;
            }
        }
        return trapped;
    }
}

Monotonic Stack

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

Reference

• LeetCode Article Solution: Trapping Rain Water
• Trapping Rain Water - GeeksforGeeks
• LeetCode – Trapping Rain Water (Java) - Program Creek
• 喜刷刷: LeetCode - Trapping Rain Water
• Yu's Garden LeetCode Question 111: Trapping Rain Water
• 水中的鱼：Trapping Rain Water 解题报告