# 42. Trapping Rain Water

Given `n` non-negative integers representing an elevation map where the width of each bar is `1`, compute how much water it can trap after raining.

**Example 1:**

![](https://assets.leetcode.com/uploads/2018/10/22/rainwatertrap.png)

<pre><code><strong>Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
</strong><strong>Output: 6
</strong><strong>Explanation: The above elevation map (black section) 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.
</strong></code></pre>

***My Solutions:***

方法1：维持一个非递增的stack。遍历高度

* 如果此时栈为空，或者当前高度小于等于栈顶高度，则把当前高度的坐标压入栈，注意这里不直接把高度压入栈，而是把坐标压入栈，这样方便在后来算水平距离。
* 当遇到比栈顶高度大的高度，说明有可能会有坑存在，可以装雨水。
  * 此时栈里至少有一个高度，如果只有一个的话，那么不能形成坑，直接跳过
  * 如果多余一个的话，把栈顶元素取出来当作坑，新的栈顶元素就是左边界，当前高度是右边界。坑的高度是（这二者较小者-减去坑的高度），长度就是右边界坐标减去左边界坐标再减1，二者相乘就是盛水量

Time: O(n); Space: O(n)

```java
public int trapRainWater(int[] heights) {
    Stack<Integer> stack = new Stack<>();
    int i = 0, res = 0;
    while (i < heights.length) {
        if (stack.isEmpty() || heights[i] <= heights[stack.peek()]) {
            stack.push(i);
            i++;
        } else {
            int bottom = stack.pop();
            if (stack.isEmpty()) continue;
            // 注意这里left是不pop出来的，因为可以继续形成坑
            int left = stack.peek();
            // System.out.println("poped bottom = " + bottom + "; left = " + left + "; right = " + i);
            int h = Math.min(heights[i], heights[left]) - heights[bottom], w = i - left - 1;
            int water = h * w;
            // System.out.println("water is " + water);
            res += water;
            // 注意这里是不进行i++的，因为还要继续判断当前的位置是不是还能继续形成坑
        }
    }
    return res;
}a
```

方法2：

对于每一个柱子来说，找到它两边比它高的棍子高度的较小者，就是这个水柱的高度。

![](https://3140251282-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-L9mNqXfPqoVkVgLGF9r%2Fuploads%2F085TfmUmPUoA79lo0rWF%2Fimage.png?alt=media\&token=b0266d49-951b-463d-a480-4a692ba293a2)

```java
public int trap(int[] height) {
    int sum = 0;
    
    //两端不用考虑
    for (int i = 1; i < height.length - 2; i++) {
        int maxLeft = 0;
        //找到左边最高墙,从当前列从右往左遍历
        for (int j = i - 1; j >= 0; j--) {
            if (height[j] > maxLeft) {
                maxLeft = height[j];
            }
        }
        int maxRight = 0;
        //找出右边最高墙，从当前列从左往右遍历
        for (int j = i + 1; j < height.length; j++) {
            if (height[j] > maxRight) {
                maxRight = height[j];
            }
        }
        //比较两端最高墙，找出较矮的墙
        int min = Math.min(maxLeft, maxRight);
        if (min > height[i]) {
            sum += (min - height[i]);
        }
    }
    return sum;
}
```

Time: O(N^2); Space: O(1)

![](https://3140251282-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-L9mNqXfPqoVkVgLGF9r%2Fuploads%2FQ7Iwuvktr2BjgInjyqjQ%2Fimage.png?alt=media\&token=dddfb341-478a-423d-84c1-d6cf94e25410)

方法3：记录下第i列左边和右边最高棍子的高度

```java
public int trap(int[] height) {
    int sum = 0;
    int[] maxLeft = new int[height.length], maxRight = new int[height.length];
    
    for (int i = 1; i < height.length-1; i++) {
        maxLeft[i] = Math.max(maxLeft[i-1], height[i-1]);
    }
    for (int i = height.length-2; i >= 0; i--) {
        maxRight[i] = Math.max(maxRight[i+1], height[i+1]);
    }
    
    for (int i = 1; i < height.length - 1; i++) {
        int min = Math.min(maxLeft[i], maxRight[i]);
        if (min > height[i]) {
            sum += (min-height[i]);
        }
    }
    return sum;
}
```

Time: O(N); Space: O(N)

方法4：双指针解法

在这个解法中，leftMax和rightMax代表的是`height[0..left]`和`height[right..end]`的最高柱子高度。

```java
public int trap(int[] heights) {
    int l = 0, r = heights.length - 1, res = 0;
    int leftMax = heights[0], rightMax = heights[ - 1];
    while (l <= r) {
        leftMax = Math.max(leftMax, heights[l]);
        rightMax = Math.max(rightMax, heights[r]);

        if (leftMax <= rightMax) {
            res += leftMax - heights[l];
            l++;
        } else {
            res += rightMax - heights[r];
            r--;
        }
    }
    return res;
}
```

![](https://3140251282-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-L9mNqXfPqoVkVgLGF9r%2Fuploads%2FzOjsiSXMiionnkhCHaWs%2Fimage.png?alt=media\&token=dcbf239f-2b89-4791-984b-ca268d78d359)

此时的`l_max`是`left`指针左边的最高柱子，但是`r_max`并不一定是`left`指针右边最高的柱子。因为我们只在乎`min(l_max, r_max)`，对于上图的情况，我们已经知道`l_max < r_max`了，至于这个`r_max`是不是右边最大的，不重要，**重要的是`height[i]`能够装的水只和`l_max`有关。**

![](https://3140251282-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-L9mNqXfPqoVkVgLGF9r%2Fuploads%2FL9NbdZemWywswHK0gL4G%2Fimage.png?alt=media\&token=96f47f7e-02f7-4db2-9f30-a51fbaa9a35f)

Time: O(n); Space: O(1)
