当前位置： 面试刷题>> 接雨水 (经典算法题500道)
### 题目描述补充
题目：**接雨水**
给定一个整数数组 `height`，其中 `height[i]` 代表坐标索引为 `i` 的位置的高度。这里，我们假设天降暴雨之后，只有高度比它两侧都高的位置可以积水（我们称这些位置为“洼地”）。每一单位宽度的“洼地”可以积存的水量等于它两侧高度的较小值减去它自己的高度。你需要计算按此规则，数组中接到的雨水量总和。
### 示例
**输入**: `height = [0,1,0,2,1,0,1,3,2,1,2,1]`
**输出**: 6
**解释**:
坐标 0, 1, 2 处的洼地可以积水，积水量分别为 0, 1, 0。
坐标 4, 5, 6 处的洼地可以积水，积水量分别为 1, 0, 1。
坐标 8, 9, 10 处的洼地可以积水，积水量分别为 0, 0, 2。
总和为 0 + 1 + 0 + 1 + 0 + 1 + 0 + 0 + 2 = 6。
### PHP 示例代码
```php
function trap($height) {
$n = count($height);
if ($n <= 2) {
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]);
}
$totalWater = 0;
for ($i = 1; $i < $n - 1; $i++) {
$totalWater += min($leftMax[$i], $rightMax[$i]) - $height[$i];
}
return $totalWater;
}
// 测试示例
$height = [0,1,0,2,1,0,1,3,2,1,2,1];
echo trap($height); // 输出 6
```
### Python 示例代码
```python
def trap(height):
n = len(height)
if n <= 2:
return 0
left_max = [0] * n
right_max = [0] * n
left_max[0] = height[0]
for i in range(1, n):
left_max[i] = max(left_max[i - 1], height[i])
right_max[n - 1] = height[n - 1]
for i in range(n - 2, -1, -1):
right_max[i] = max(right_max[i + 1], height[i])
total_water = 0
for i in range(1, n - 1):
total_water += min(left_max[i], right_max[i]) - height[i]
return total_water
# 测试示例
height = [0,1,0,2,1,0,1,3,2,1,2,1]
print(trap(height)) # 输出 6
```
### JavaScript 示例代码
```javascript
function trap(height) {
const n = height.length;
if (n <= 2) {
return 0;
}
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 totalWater = 0;
for (let i = 1; i < n - 1; i++) {
totalWater += Math.min(leftMax[i], rightMax[i]) - height[i];
}
return totalWater;
}
// 测试示例
const height = [0,1,0,2,1,0,1,3,2,1,2,1];
console.log(trap(height)); // 输出 6
```
**码小课** 网站中有更多关于算法和数据结构的内容分享给大家学习，欢迎访问并深入学习！