> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/my-algorithm-summary/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/my-algorithm-summary/data-structure/stack/monotone-stack/42-trapping-rain-water.md).

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

![](http://www.leetcode.com/static/images/problemset/rainwatertrap.png)

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)

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