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

LeetCode 407. 接雨水 II 题目描述 给你一个 m x n 的矩阵，其中的值均为非负整数，代表二维高度图。每个单元的长方体高度由对应的数值表示。请计算此形状在降雨后能接多少体积的雨水。 例如，给定一个 3x3 的高度图： 我们需要计算这个“凹凸不平”的二维地形能积蓄多少雨水。 解题过程 这个问题是经典的一维“接雨水”问题的二维扩展。在一维问题中，我们可以通过动态规划或双指针高效解决。但在二维中，水可以从任意方向流动，情况复杂得多。 核心思路：木桶原理 一个单元能接多少水，取决于它周围最低的“屏障”高度。但关键在于，这个“屏障”不是仅仅看相邻的四个格子，因为水可能会从更远的地方，通过一条路径“泄漏”出去。例如，即使一个单元被较高的格子包围，但如果这些格子之外有一个较低的边界，水依然会流走。 突破口：从边界向内收缩 想象一下，雨水是从边界开始向内填充的。最外一圈的格子是“围墙”，它们的高度决定了初始的“水位”。但水位不是固定的，因为围墙本身可能高低不平。水会从最低的围墙处先“漫”进来。 这引出了我们的算法： 最小堆（优先队列）BFS 。 循序渐进讲解 步骤一：初始化与数据结构 如果矩阵的行数 m 或列数 n 小于 3，那么无法形成任何蓄水空间，直接返回 0。 我们需要一个最小堆（优先队列）。堆中存储的是三元组 (height, x, y) ，表示在位置 (x, y) 处的当前有效水位高度（或围墙高度）。堆按照 height 进行排序，总是让当前最小的元素出堆。这保证了我们总是从当前已知的“最低点”开始处理。 我们需要一个二维布尔数组 visited ，大小与矩阵相同，用来记录哪些位置已经被处理过，避免重复计算。 初始化：将矩阵的最外一圈（所有边界格子）全部加入最小堆，并将它们标记为已访问。因为这些边界格子是初始的“围墙”，水无法被积蓄在它们之上，它们的高度就是当前边界的水位。 步骤二：处理过程（BFS） 当最小堆不为空时，弹出堆顶元素。这个元素是当前我们已知的“最低水位线”，记其高度为 currHeight ，位置为 (x, y) 。 检查这个最低点 (x, y) 的 四个方向 （上、下、左、右）的邻居 (nx, ny) 。 如果邻居 (nx, ny) 是合法坐标（在矩阵范围内）且 未被访问过 ： a. 关键计算 ：如果邻居格子自身的实际高度 heightMap[nx][ny] 低于当前的水位线 currHeight ，那么它们之间的高度差 (currHeight - heightMap[nx][ny]) 就是该邻居格子能接住的雨水量。因为当前水位线 currHeight 就像一个木桶的短板，水会填充到这个高度。 b. 将计算出的雨水量累加到总结果中。 c. 将这个邻居格子 (nx, ny) 加入最小堆。但是，加入堆中的高度值应该是 max(currHeight, heightMap[nx][ny]) 。为什么？ - 如果 heightMap[nx][ny] < currHeight ：这个邻居格子被填充后，它的有效高度就变成了 currHeight （水填满了它）。它现在成为了新的“围墙”的一部分。 - 如果 heightMap[nx][ny] >= currHeight ：这个邻居格子本身就是一个较高的“支柱”，它不会被水淹没，它的有效高度就是它自身的高度 heightMap[nx][ny] 。它直接成为了新的、更高的“围墙”。 d. 将邻居格子 (nx, ny) 标记为已访问。 步骤三：结束与返回 当最小堆为空，意味着所有格子都已经被处理完毕。此时累加的总雨水量就是最终的答案。 为什么这个算法是正确的？ 算法的精髓在于，我们总是从当前“水位”最低的地方开始向内探索。这模拟了水从最低的边界点流入内部的过程。 一个内部格子能接多少水，不取决于它紧邻的格子，而是取决于水流入它所在“洼地”的那个入口的高度（即从边界到该格子的路径上的最大高度的最小值）。我们的算法通过优先处理最低点，恰好保证了这个“入口高度”是最优的。 通过最小堆，我们动态地更新“水位”。当一个低点被处理后，它周围未被访问的格子就有了一个新的、已知的参考水位。这个过程像涟漪一样从边界向内扩散，确保每个格子的蓄水量都是根据它所能接触到的实际最低“海平面”来计算的。 总结 解决这个问题的关键是转变视角，从“每个格子能装多少水”转变为“水如何从边界流入”。使用 最小堆+BFS 的策略，可以智能地找到水流动的路径（总是从低到高），并准确计算出每个位置的积水量。这个方法高效且直观，是解决此类二维蓄水问题的经典方案。