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

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

PreviousTriangle Count NextContainer with Most Water

Last updated 3 years ago