# 42 Trapping Rain Water

## 42. [Trapping Rain Water](https://leetcode.com/problems/trapping-rain-water/description/)

## 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]`, return`6`.

## 2. Implementation

**(1) Two Pointers**

```java
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)

```java
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)
