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.

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.

2. Implementation

思路：

(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 n = height.length;
        int water = 0, curHeight = 0, width = 0;
        int res = 0;

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

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

3. Time & Space Complexity

时间和空间都是O(n)