题目描述补充

题目：接雨水

给定一个整数数组 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 示例代码

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 示例代码

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 示例代码

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

码小课 网站中有更多关于算法和数据结构的内容分享给大家学习，欢迎访问并深入学习！