# 0042. 接雨水

### 题目地址(42. 接雨水)

<https://leetcode-cn.com/problems/trapping-rain-water/>

### 题目描述

```
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。


```

![42.trapping-rain-water-1](https://p.ipic.vip/cghgbn.jpg)

```
上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。

示例:

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

```

### 前置知识

* 空间换时间
* 双指针
* 单调栈

### 公司

* 阿里
* 腾讯
* 百度
* 字节

### 双数组

#### 思路

这是一道雨水收集的问题， 难度为`hard`. 如图所示，让我们求下过雨之后最多可以积攒多少的水。

如果采用暴力求解的话，思路应该是枚举每一个位置 i 下雨后的积水量，累加记为答案。

* 伪代码

```js
for (let i = 0; i < height.length; i++) {
  area += (h[i] - height[i]) * 1; // h为下雨之后的水位
}
```

问题转化为求 h 数组，这里 h\[i] 其实等于`左右两侧柱子的最大值中的较小值`，即 `h[i] = Math.min(左边柱子最大值, 右边柱子最大值)`

如上图那么 h 为 \[0, 1, 1, 2, 2, 2 ,2, 3, 2, 2, 2, 1]

问题的关键在于求解`左边柱子最大值`和`右边柱子最大值`, 我们其实可以用两个数组来表示`leftMax`, `rightMax`， 以 leftMax 为例，leftMax\[i]代表 i 的左侧柱子的最大值，因此我们维护两个数组即可。

#### 关键点解析

* 建模 `h[i] = Math.min(左边柱子最大值, 右边柱子最大值)`(h 为下雨之后的水位)

#### 代码

* 代码支持: JS, Python3, C++:

JS Code:

```js
/*
 * @lc app=leetcode id=42 lang=javascript
 *
 * [42] Trapping Rain Water
 *
 */
/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function (height) {
  let max = 0;
  let volume = 0;
  const leftMax = [];
  const rightMax = [];

  for (let i = 0; i < height.length; i++) {
    leftMax[i] = max = Math.max(height[i], max);
  }

  max = 0;

  for (let i = height.length - 1; i >= 0; i--) {
    rightMax[i] = max = Math.max(height[i], max);
  }

  for (let i = 0; i < height.length; i++) {
    volume = volume + Math.min(leftMax[i], rightMax[i]) - height[i];
  }

  return volume;
};
```

Python Code:

```python
class Solution:
    def trap(self, heights: List[int]) -> int:
        n = len(heights)
        l, r = [0] * n, [0] * n
        ans = 0
        for i in range(1, len(heights)):
            l[i] = max(l[i - 1], heights[i - 1])
        for i in range(len(heights) - 2, 0, -1):
            r[i] = max(r[i + 1], heights[i + 1])
        for i in range(len(heights)):
            ans += max(0, min(l[i], r[i]) - heights[i])
        return ans

```

C++ Code:

```c++
int trap(vector<int>& heights)
{
	if(heights == null)
		return 0;
    int ans = 0;
    int size = heights.size();
    vector<int> left_max(size), right_max(size);
    left_max[0] = heights[0];
    for (int i = 1; i < size; i++) {
        left_max[i] = max(heights[i], left_max[i - 1]);
    }
    right_max[size - 1] = heights[size - 1];
    for (int i = size - 2; i >= 0; i--) {
        right_max[i] = max(heights[i], right_max[i + 1]);
    }
    for (int i = 1; i < size - 1; i++) {
        ans += min(left_max[i], right_max[i]) - heights[i];
    }
    return ans;
}

```

**复杂度分析**

* 时间复杂度：$O(N)$
* 空间复杂度：$O(N)$

### 双指针

这种解法为进阶解法， 大家根据自己的情况进行掌握。

#### 思路

上面代码比较好理解，但是需要额外的 N 的空间。从上面解法可以看出，我们实际上只关心左右两侧较小的那一个，并不需要两者都计算出来。具体来说：

* 如果 l\[i + 1] < r\[i] 那么 最终积水的高度由 i 的左侧最大值决定。
* 如果 l\[i + 1] >= r\[i] 那么 最终积水的高度由 i 的右侧最大值决定。

因此我们不必维护完整的两个数组，而是可以只进行一次遍历，同时维护左侧最大值和右侧最大值，使用常数变量完成即可。这是一个典型的双指针问题，

具体算法：

1. 维护两个指针 left 和 right，分别指向头尾。
2. 初始化左侧和右侧最高的高度都为 0。
3. 比较 height\[left] 和 height\[right]
   * 3.1 如果 height\[left] < height\[right], 那么瓶颈在于 height\[left]，不需要考虑 height\[right]
     * 3.1.1 如果 height\[left] < left\_max， 则当前格子积水面积为(left\_max - height\[left])，否则无法积水，即积水面积为 0。也可将逻辑统一为盛水量为 max(0, left\_max - height\[left])
     * 3.1.2 左指针右移一位。（其实就是左指针的位置的雨水量已经计算完成了，我们移动到下个位置用同样的方法计算）
   * 3.2 否则 瓶颈在于 height\[right]，不需要考虑 height\[left]
     * 3.2.1 如果 height\[right] < right\_max, 则当前格子积水面积为(right\_max - height\[left])，否则无法积水，即积水面积为 0。也可将逻辑统一为盛水量为 max(0, right\_max - height\[right])
     * 3.2.2 右指针右移一位。（其实就是右指针的位置的雨水量已经计算完成了，我们移动到下个位置用同样的方法计算）

#### 代码

* 代码支持: Python, C++, Go, PHP:

Python Code:

```python
class Solution:
    def trap(self, heights: List[int]) -> int:
        n = len(heights)
        l_max = r_max = 0
        l, r = 0, n - 1
        ans = 0
        while l < r:
            if heights[l] < heights[r]:
                if heights[l] < l_max:
                    ans += l_max - heights[l]
                else:
                    l_max = heights[l]
                l += 1
            else:
                if heights[r] < r_max:
                    ans += r_max - heights[r]
                else:
                    r_max = heights[r]
                r -= 1
        return ans
```

C++ Code:

```c++

class Solution {
public:
    int trap(vector<int>& heights)
{
    int left = 0, right = heights.size() - 1;
    int ans = 0;
    int left_max = 0, right_max = 0;
    while (left < right) {
        if (heights[left] < heights[right]) {
            heights[left] >= left_max ? (left_max = heights[left]) : ans += (left_max - heights[left]);
            ++left;
        }
        else {
            heights[right] >= right_max ? (right_max = heights[right]) : ans += (right_max - heights[right]);
            --right;
        }
    }
    return ans;
}

};
```

Go Code:

```go
func trap(height []int) int {
    if len(height) == 0 {
        return 0
    }

    l, r := 0, len(height)-1
    lMax, rMax := height[l], height[r]
    ans := 0
    for l < r {
        if height[l] < height[r] {
            if height[l] < lMax {
                ans += lMax - height[l]
            } else {
                lMax = height[l]
            }
            l++
        } else {
            if height[r] < rMax {
                ans += rMax - height[r]
            } else {
                rMax = height[r]
            }
            r--
        }
    }
    return ans
}
```

PHP Code:

```php
class Solution
{

    /**
     * @param Integer[] $height
     * @return Integer
     */
    function trap($height)
    {
        $n = count($height);
        if (!$n) return 0;

        $l = 0;
        $l_max = $height[$l];
        $r = $n - 1;
        $r_max = $height[$r];
        $ans = 0;
        while ($l < $r) {
            if ($height[$l] < $height[$r]) {
                if ($height[$l] < $l_max) $ans += $l_max - $height[$l];
                else $l_max = $height[$l];
                $l++;
            } else {
                if ($height[$r] < $r_max) $ans += $r_max-$height[$r];
                else $r_max = $height[$r];
                $r--;
            }
        }
        return $ans;
    }
}
```

**复杂度分析**

* 时间复杂度：$O(N)$
* 空间复杂度：$O(1)$

### 相关题目

* [84.largest-rectangle-in-histogram](/leetcode-solution/hard/84.largest-rectangle-in-histogram.md)

更多题解可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 37K star 啦。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。

![](https://p.ipic.vip/ywgwz4.jpg)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/hard/42.trapping-rain-water.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.