LeetCode 407. 接雨水 II

字数 2092 2025-10-30 08:32:28

LeetCode 407. 接雨水 II

题目描述

给你一个 m x n 的矩阵，其中的值均为非负整数，代表二维高度图。每个单元的长方体高度为对应的值。请计算此形状最多能接住多少体积的雨水。

例如，给定如下高度图：

[
  [1,4,3,1,3,2],
  [3,2,1,3,2,4],
  [2,3,3,2,3,1]
]

直观上看，雨水会被框在由较高单元格构成的“边界”内。我们需要计算所有能蓄水的位置所能容纳的雨水总量。

解题过程

这个问题是经典一维“接雨水”问题的二维扩展。核心思想是：一个单元格能接多少雨水，不取决于它周围四个方向的最大值，而是取决于它到边界的所有路径上，遇到的最高点中的最小值（即“木桶原理”的二维版本）。水会从最低的边界处流出，因此一个单元格的水位最高只能达到其所有外流路径上最低的那个最高点的高度。

一个非常高效的策略是使用最小堆（优先队列）的广度优先搜索（BFS），也常被称为“木桶原理”BFS。

初始化与核心洞察
- 首先，最外圈的单元格是天然的“边界”。它们无法接住任何雨水，因为水会从它们那里流走。
- 但是，这些边界的高度，决定了其相邻内侧单元格水位的可能上限。
- 想象一下，我们从边界最低的点开始向内注水。因为水总是往低处流，当前最低边界的高度，就是其相邻内侧区域水位能到达的极限（如果内侧单元格比这个边界低的话）。
算法步骤
- 步骤一：创建数据结构并初始化边界
  - 创建一个最小堆（优先队列），用于存储单元格的坐标 (row, col) 和其高度 height。堆按照高度进行排序，高度最小的单元格位于堆顶。
  - 创建一个与输入矩阵同等大小的二维布尔数组 visited，用于标记哪些单元格已经被处理过。
  - 初始化：遍历整个矩阵的最外圈（第一行、最后一行、第一列、最后一列）。
    - 将每个边界单元格 (i, j) 加入最小堆，高度为 heightMap[i][j]。
    - 同时将 visited[i][j] 标记为 true。因为这些边界单元格我们已经考虑过了。
- 步骤二：处理堆中的单元格（BFS过程）
  - 初始化一个变量 ans = 0 来累计总接水量。
  - 定义一个方向数组 dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]，表示上下左右四个方向。
  - 当最小堆不为空时，循环执行以下操作：
    a. 弹出堆顶元素：这是当前堆中高度最低的单元格，记其坐标为 (x, y)，高度为 currHeight。这个 currHeight 可以被看作是当前我们正在探索的“水位平面”的高度。任何比它低的相邻单元格，如果被它围住，就有可能蓄水。
    b. 遍历四个邻居：对于 (x, y) 的上下左右四个邻居 (nx, ny)。
    c. 检查邻居有效性：检查 (nx, ny) 是否在矩阵范围内，并且是否未被访问过 (!visited[nx][ny])。
    d. 计算接水量并更新邻居高度：
    * 如果邻居的高度 heightMap[nx][ny] 小于当前的 currHeight，这意味着邻居单元格是一个“洼地”。那么，这个洼地最多能蓄水到 currHeight 的高度。因此，积水量为 currHeight - heightMap[nx][ny]。我们将这个值加到总答案 ans 上。
    * 关键点：无论邻居原始高度是多少，当我们把它加入堆时，它作为新边界的高度应该是 max(currHeight, heightMap[nx][ny])。
    * 如果邻居原始高度低（形成了洼地），蓄水后它的有效高度就变成了 currHeight（因为水填满了洼地，这个位置现在和外面的水位一样高了）。
    * 如果邻居原始高度高，那么它本身就是一个坚固的边界，它的有效高度就是它自己的高度。
    * 将这个新的有效高度（max(currHeight, heightMap[nx][ny])）和邻居位置 (nx, ny) 一起加入最小堆。
    e. 标记为已访问：将邻居 (nx, ny) 标记为已访问 (visited[nx][ny] = true)。
算法逻辑解释
- 这个算法之所以正确，是因为它总是从当前已知的“最低边界”开始处理。
- 这个最低边界的高度，决定了它内侧区域水位的上限。我们从这里开始“灌水”，内侧任何比这个边界低的单元格都能蓄水，蓄水量就是高度差。
- 处理完一个单元格后，我们把它内侧的邻居加入考虑范围。邻居的新高度被更新为“蓄水后的高度”（即它自己和当前边界高度的最大值），这样它就成为了新的“边界”的一部分。
- 通过使用最小堆，我们保证了总是先处理最低的边界，这样就确保了当我们计算一个洼地的蓄水量时，包围这个洼地的“堤坝”的最低点已经被我们考虑过了，计算结果准确无误。

总结

解决“接雨水 II”问题的关键是利用最小堆进行BFS，始终从最低的边界点开始，向内探索并计算蓄水量。这个方法巧妙地应用了二维空间的“木桶原理”，将复杂的三维蓄水问题转化为一个基于优先级队列的图遍历问题，效率很高。

LeetCode 407. 接雨水 II 题目描述给你一个 m x n 的矩阵，其中的值均为非负整数，代表二维高度图。每个单元的长方体高度为对应的值。请计算此形状最多能接住多少体积的雨水。例如，给定如下高度图：直观上看，雨水会被框在由较高单元格构成的“边界”内。我们需要计算所有能蓄水的位置所能容纳的雨水总量。解题过程这个问题是经典一维“接雨水”问题的二维扩展。核心思想是：一个单元格能接多少雨水，不取决于它周围四个方向的最大值，而是取决于它到边界的所有路径上，遇到的最高点中的最小值（即“木桶原理”的二维版本）。水会从最低的边界处流出，因此一个单元格的水位最高只能达到其所有外流路径上最低的那个最高点的高度。一个非常高效的策略是使用最小堆（优先队列）的广度优先搜索（BFS），也常被称为“木桶原理”BFS。初始化与核心洞察首先，最外圈的单元格是天然的“边界”。它们无法接住任何雨水，因为水会从它们那里流走。但是，这些边界的高度，决定了其相邻内侧单元格水位的可能上限。想象一下，我们从边界最低的点开始向内注水。因为水总是往低处流，当前最低边界的高度，就是其相邻内侧区域水位能到达的极限（如果内侧单元格比这个边界低的话）。算法步骤步骤一：创建数据结构并初始化边界创建一个最小堆（优先队列），用于存储单元格的坐标 (row, col) 和其高度 height 。堆按照高度进行排序，高度最小的单元格位于堆顶。创建一个与输入矩阵同等大小的二维布尔数组 visited ，用于标记哪些单元格已经被处理过。初始化：遍历整个矩阵的最外圈（第一行、最后一行、第一列、最后一列）。将每个边界单元格 (i, j) 加入最小堆，高度为 heightMap[i][j] 。同时将 visited[i][j] 标记为 true 。因为这些边界单元格我们已经考虑过了。步骤二：处理堆中的单元格（BFS过程）初始化一个变量 ans = 0 来累计总接水量。定义一个方向数组 dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)] ，表示上下左右四个方向。当最小堆不为空时，循环执行以下操作： a. 弹出堆顶元素：这是当前堆中高度最低的单元格，记其坐标为 (x, y) ，高度为 currHeight 。这个 currHeight 可以被看作是当前我们正在探索的“水位平面”的高度。任何比它低的相邻单元格，如果被它围住，就有可能蓄水。 b. 遍历四个邻居：对于 (x, y) 的上下左右四个邻居 (nx, ny) 。 c. 检查邻居有效性：检查 (nx, ny) 是否在矩阵范围内，并且是否未被访问过 ( !visited[nx][ny] )。 d. 计算接水量并更新邻居高度： * 如果邻居的高度 heightMap[nx][ny] 小于当前的 currHeight ，这意味着邻居单元格是一个“洼地”。那么，这个洼地最多能蓄水到 currHeight 的高度。因此，积水量为 currHeight - heightMap[nx][ny] 。我们将这个值加到总答案 ans 上。 * 关键点：无论邻居原始高度是多少，当我们把它加入堆时，它作为新边界的高度应该是 max(currHeight, heightMap[nx][ny]) 。 * 如果邻居原始高度低（形成了洼地），蓄水后它的有效高度就变成了 currHeight （因为水填满了洼地，这个位置现在和外面的水位一样高了）。 * 如果邻居原始高度高，那么它本身就是一个坚固的边界，它的有效高度就是它自己的高度。 * 将这个新的有效高度（ max(currHeight, heightMap[nx][ny]) ）和邻居位置 (nx, ny) 一起加入最小堆。 e. 标记为已访问：将邻居 (nx, ny) 标记为已访问 ( visited[nx][ny] = true )。算法逻辑解释这个算法之所以正确，是因为它总是从当前已知的“最低边界”开始处理。这个最低边界的高度，决定了它内侧区域水位的上限。我们从这里开始“灌水”，内侧任何比这个边界低的单元格都能蓄水，蓄水量就是高度差。处理完一个单元格后，我们把它内侧的邻居加入考虑范围。邻居的新高度被更新为“蓄水后的高度”（即它自己和当前边界高度的最大值），这样它就成为了新的“边界”的一部分。通过使用最小堆，我们保证了总是先处理最低的边界，这样就确保了当我们计算一个洼地的蓄水量时，包围这个洼地的“堤坝”的最低点已经被我们考虑过了，计算结果准确无误。总结解决“接雨水 II”问题的关键是利用最小堆进行BFS，始终从最低的边界点开始，向内探索并计算蓄水量。这个方法巧妙地应用了二维空间的“木桶原理”，将复杂的三维蓄水问题转化为一个基于优先级队列的图遍历问题，效率很高。