LeetCode 「困难」42.接雨水

sankigan2025-3-6算法LeetCode

接雨水open in new window

题目描述

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

示例

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6

输入：height = [4,2,0,3,2,5]
输出：9

解答

暴力法

关键思路

对于每个柱子，找到它左边和右边的最高柱子，然后计算当前柱子能接的雨水量。

具体步骤

遍历每个柱子
对于每个柱子，向左遍历找到左边的最高柱子
向右遍历找到右边的最高柱子
当前柱子能接的雨水量为 min(左边最高, 右边最高) - 当前柱子高度
将所有柱子的雨水量累加

Code

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
  let sum = 0;

  for (let i = 0; i < height.length; ++i) {
    // 计算左边最高柱子
    let leftMaxHeight = 0;
    for (let j = 0; j <= i; ++j) {
      leftMaxHeight = Math.max(leftMaxHeight, height[j]);
    }

    // 计算右边最高柱子
    let rightMaxHeight = 0;
    for (let j = i; j < height.length; ++j) {
      rightMaxHeight = Math.max(rightMaxHeight, height[j]);
    }

    // 累加雨水量（确保不为负数）
    sum += Math.min(leftMaxHeight, rightMaxHeight) - height[i];
  }

  return sum;
};

Tips：为什么要包含当前柱子？

接雨水的定义：接雨水的条件是当前柱子比左右两边的最高柱子低，才能形成“凹槽”接住雨水
计算左边最高柱子：如果包含当前柱子，那么 leftMaxHeight 表示的是从最左边到当前柱子（包括当前柱子）的最高高度
计算右边最高柱子：如果包含当前柱子，那么 rightMaxHeight 表示的是从当前柱子（包括当前柱子）到最右边的最高高度
为什么包含当前柱子：
- 如果当前柱子本身就是左边或右边的最高柱子，那么 Math.min(leftMaxHeight, rightMaxHeight) - height[i] 会得到 0，表示当前柱子不能接住雨水
- 这样可以避免错误地累加负数的雨水量

动态规划

关键思路

预先计算每个柱子的左边最高和右边最高，避免重复计算

具体步骤

创建两个数组 left_max 和 right_max，分别存储每个柱子左边和右边的最高柱子
从左到右遍历一次，填充 left_max
从右到左遍历一次，填充 right_max
最后遍历每个柱子，计算雨水量并累加

Code

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
  const n = height.length;
  if (n === 0) return 0;

  // 初始化 leftMax 和 rightMax 数组
  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 sum = 0;
  for (let i = 0; i < n; ++i) {
    sum += Math.min(leftMax[i], rightMax[i]) - height[i];
  }

  return sum;
};

双指针

关键思路

使用两个指针从两端向中间移动，同时维护左右两边的最高柱子

具体步骤

初始化两个指针 left 和 right，分别指向数组的开头和结尾
初始化 left_max 和 right_max 为 0
当 left < right 时：

如果 height[left] < height[right]：
- 如果 height[left] >= left_max，更新 left_max
- 否则，累加雨水量 left_max - height[left]
- 移动 left 指针向右
否则：
- 如果 height[right] >= right_max，更新 right_max
- 否则，累加雨水量 right_max - height[right]
- 移动 right 指针向左

Code

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
  // 左指针
  let left = 0;
  // 右指针
  let right = height.length - 1;
  // 从左到右的最高柱子高度
  let leftMax = 0;
  // 从右到左的最高柱子高度
  let rightMax = 0;
  // 总雨水量
  let sum = 0;

  while (left < right) {
    // 如果左边柱子较低，雨水的量就由左边的最高柱子决定
    if (height[left] < height[right]) {
      // 如果当前柱子比 leftMax 高，更新 leftMax
      if (height[left] > leftMax) {
        leftMax = height[left];
      } else {
        // 否则累加雨水量
        sum += leftMax - height[left];
      }
      // 移动左指针
      ++left;
    }
    // 如果右边柱子较低，雨水的量就由右边的最高柱子决定
    else {
      // 如果当前柱子比 rightMax 高，更新 rightMax
      if (height[right] > rightMax) {
        rightMax = height[right];
      } else {
        // 否则累加雨水量
        sum += rightMax - height[right];
      }
      // 移动右指针
      --right;
    }
  }

  return sum;
};

Tips：为什么左边柱子较低，雨水的量由左边的最高柱子决定？

右边的柱子较高：由于 height[left] < height[right], 右边的柱子已经比左边的柱子高，因此右边的柱子不会限制雨水的量
左边的最高柱子决定雨水量：当前柱子能接住的雨水量取决于它左边的最高柱子（leftMax）和它右边的最高柱子（rightMax）中较矮的那一个。由于右边的柱子较高，min(leftMax, rightMax) 实际上等于 leftMax
雨水量计算：当前柱子能接住的雨水量为 leftMax - height[left]

LeetCode 「困难」42.接雨水

ON THIS PAGE