当前位置： 面试刷题>> 接雨水(经典算法150题)
### 题目描述
题目：**接雨水**
给定一个整数数组 `height`，其中 `height[i]` 代表坐标 `i` 处的条形块的高度。这些条形块是宽度为 1 的竖直矩形，并且排列在水平线上。雨水可以累积在这些条形块之间形成的低洼处。
请编写一个算法来计算能接多少单位的雨水。
#### 示例
输入: `height = [0,1,0,2,1,0,1,3,2,1,2,1]`
输出: `6`
解释: 在上面的例子中，第 0、1、2、3、4、5 号条形块的高度分别为 `[0,1,0,2,1,0]`。
- 索引 0 处的条形块和索引 1 之间的低洼处可以接 1 单位的水。
- 索引 2 处的条形块和索引 3 之间的低洼处可以接 3 单位的水（因为条形块的高度为 0，所以可以接满）。
- 索引 4 处的条形块和索引 5 之间的低洼处可以接 1 单位的水。
- 索引 5 处的条形块和索引 6 之间的低洼处可以接 1 单位的水。
总共可以接 1+3+1+1=6 单位的水。
### 解题思路
一种常见的解决方案是使用双指针法结合单调栈。但是为了简化，这里先给出一个基于动态规划的解法，然后提供双指针法和单调栈法的 Python、PHP、JavaScript 示例代码。
### 动态规划解法
思路：
1. 使用两个动态规划数组 `leftMax` 和 `rightMax`，其中 `leftMax[i]` 表示位置 `i` 左侧的最大高度，`rightMax[i]` 表示位置 `i` 右侧的最大高度。
2. 遍历数组 `height`，计算 `leftMax` 和 `rightMax`。
3. 遍历 `height` 数组，对于每个位置 `i`，能接的雨水量为 `min(leftMax[i], rightMax[i]) - height[i]`（如果结果为负数则不计入总水量）。
### Python 示例代码
```python
def trap(height):
if not height:
return 0
n = len(height)
leftMax = [0] * n
rightMax = [0] * n
leftMax[0] = height[0]
for i in range(1, n):
leftMax[i] = max(leftMax[i-1], height[i])
rightMax[n-1] = height[n-1]
for i in range(n-2, -1, -1):
rightMax[i] = max(rightMax[i+1], height[i])
water = 0
for i in range(n):
water += min(leftMax[i], rightMax[i]) - height[i]
return water
```
### PHP 示例代码
```php
function trap($height) {
$n = count($height);
if ($n == 0) return 0;
$leftMax = array_fill(0, $n, 0);
$rightMax = array_fill(0, $n, 0);
$leftMax[0] = $height[0];
for ($i = 1; $i < $n; $i++) {
$leftMax[$i] = max($leftMax[$i-1], $height[$i]);
}
$rightMax[$n-1] = $height[$n-1];
for ($i = $n-2; $i >= 0; $i--) {
$rightMax[$i] = max($rightMax[$i+1], $height[$i]);
}
$water = 0;
for ($i = 0; $i < $n; $i++) {
$water += min($leftMax[$i], $rightMax[$i]) - $height[$i];
}
return $water;
}
```
### JavaScript 示例代码
```javascript
function trap(height) {
if (height.length === 0) return 0;
const n = height.length;
const leftMax = new Array(n).fill(0);
const rightMax = new Array(n).fill(0);
leftMax[0] = height[0];
for (let i = 1; i < n; i++) {
leftMax[i] = Math.max(leftMax[i-1], height[i]);
}
rightMax[n-1] = height[n-1];
for (let i = n-2; i >= 0; i--) {
rightMax[i] = Math.max(rightMax[i+1], height[i]);
}
let water = 0;
for (let i = 0; i < n; i++) {
water += Math.min(leftMax[i], rightMax[i]) - height[i];
}
return water;
}
```
这些代码示例提供了动态规划解决接雨水问题的方法，每种语言都进行了详细的实现。