42 Trapping Rain Water

42. Trapping Rain Water

1. Question

Givennnon-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], return6.

2. Implementation

(1) Two Pointers

class Solution {
    public int trap(int[] height) {
        if (height == null || height.length <= 1) {
            return 0;
        }

        int left = 0, right = height.length - 1;
        int leftMaxHeight = height[left], rightMaxHeight = height[right];
        int res = 0;

        while (left < right) {
            if (height[left] < height[right]) {
                ++left;
                leftMaxHeight = Math.max(leftMaxHeight, height[left]);
                res += leftMaxHeight - height[left];
            }
            else {
                --right;
                rightMaxHeight = Math.max(rightMaxHeight, height[right]);
                res += rightMaxHeight - height[right];
            }
        }
        return res;
    }
}

(2) Monotone Stack

思路：(1) 凹陷处可以积水。所以寻找先递减后递增的位置就可以了

(2) 维护一个单调递减的Stack，当heights[stack.peek()] <= heights[i], 找到凹陷处，出栈，计算可蓄水的体积

(3) 计算体积时，以bottomIndex作为中点，向两边找出比它高的bar(corner case: 如果此时stack为空，则无法找到左边的bar)

class Solution {
    public int trap(int[] height) {
        Stack<Integer> stack = new Stack<>();
        int res = 0, water = 0;

        for (int i = 0; i < height.length; i++) {
            while (!stack.isEmpty() && height[stack.peek()] <= height[i]) {
                int bottomIndex = stack.pop();

                if (stack.isEmpty()) {
                    water = 0;
                }
                else {
                    int width = i - stack.peek() - 1;
                    int h = Math.min(height[stack.peek()], height[i]) - height[bottomIndex];
                    water = width * h;
                }
                res += water;
            }
            stack.push(i);
        }
        return res;
    }
}

3. Time & Space Complexity

Two Pointers: 时间复杂度O(n), 空间复杂度O(1)

Monotone Stack: 时间复杂度O(n), 空间复杂度O(n)