当前位置： 面试刷题>> 接雨水(经典算法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 示例代码

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

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

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;
}

这些代码示例提供了动态规划解决接雨水问题的方法，每种语言都进行了详细的实现。

推荐面试题