在本篇文章中，我们将深入探讨一个非常经典且具有挑战性的算法问题：如何在二维矩阵中计算降雨后能截留的总体积。如果你熟悉“接雨水”问题，你会知道它在面试和实际开发中都是考察逻辑思维与数据结构应用的好题目。而在二维矩阵中解决这个问题，需要我们将贪心策略与优先队列（最小堆）巧妙结合。准备好和我们一起探索这个算法的奥秘了吗？我们将从核心原理讲起，带你一步步拆解解题思路，并提供经过优化的代码实现。
问题陈述与核心挑战
首先，让我们明确一下我们要解决的具体问题。给定一个由正整数组成的 M x N 维矩阵，矩阵中的每个数字 arr[i][j] 代表该位置单元格的高度。想象一下，雨水落在这个由不同高度的柱子组成的“地图”上。雨水会流向高度更低的地方，或者流出到矩阵边界之外。我们的任务是计算出降雨后，这个矩阵内部总共能截留多少体积的雨水。
为什么这个问题具有挑战性？在一维场景下，我们只需要找到当前柱子左右两边的最高墙，就能确定当前柱子能存多少水。但在二维矩阵中，水不仅受限于左右和上下的柱子，而且水是可以绕过障碍物流动的。这意味着，我们不能简单地分别计算行和列的存水量，必须考虑水在二维平面上的流动性和“木桶效应”——即水位取决于最短的那块木板（或者说最低的边界）。
示例分析：直观理解
在深入代码之前，让我们通过一个直观的例子来理解题目。
示例 1：
假设输入矩阵 arr[][] 为：
{
{4, 2, 7},
{2, 1, 10},
{5, 10, 2}
}
输出： 1
让我们一步步来分析雨水是如何被截留的：
- 边界行为：位于矩阵边缘的单元格，如 (0,0), (0,1) 等，因为直接连通矩阵外部，所以它们无法截留雨水，水会直接流走。我们称之为“边界单元”。
- 内部单元 (1, 1)：这个位置的高度是 1。让我们看看它的周围：
* 上方 (0,1) 高度 2
* 左侧 (1,0) 高度 2
* 下方 (2,1) 高度 10
* 右侧 (1,2) 高度 7
这里初看似乎能存水，但别忘了水会往低处流。注意单元格 (2,2)，它的高度是 2。在 (2,2) 的周围，有一个巨大的“挡板” (1,2) 高度 7，以及 (2,1) 高度 10。水实际上倾向于聚集在低洼处。
让我们换个角度：水最终能否留住，取决于周围是否存在一个完全封闭的、比当前单元格更高的“堤坝”。
在这个例子中，关键是 (2,2) 位置。虽然它本身是边界，但它的邻居 (2,1) 是 10，(1,2) 是 7。这看起来像是个开口，但实际上，我们关注的是内部。让我们重新聚焦到内部单元格 (1,1) (高度1)。它被 2, 2, 10, 7 包围。如果注入水，水位会上升，直到找到一个溢出点。
实际上，这题的关键在于连通性。如果我们看整个系统，最低的边界是高度 1（位置(1,1)自身）或者高度 2（位置(0,1)等）。由于 (1,1) 高度最低（1），而它紧邻着高度为 2 的边界（(0,1) 或 (1,0)），且没有形成完全封闭的更高圈，大部分水会流走。但是，对于 (2,2) 或者特定的内部低洼点，我们需要算法来判断。
修正的解释（基于算法逻辑）：
实际上，这个矩阵的内部只有 (1,1) 不是边界。(1,1) 的高度是 1。它的邻居最小高度是 2。所以 (1,1) 理论上可以存 1 单位的水（2-1=1）。但是，这 1 单位的水会流走吗？
看它的邻居：(0,1)=2, (1,0)=2, (1,2)=7, (2,1)=10。如果 (1,1) 变成 2，它会溢出到 (0,1) 或 (1,0) 吗？是的，因为 (0,1) 和 (1,0) 是高度为 2 的边界。水会从那里流出。所以严格来说，这个矩阵可能存不住水？
让我们仔细审视题目给出的“输出：1”。这意味着我的直觉可能忽略了某些细微之处，或者题目示例有特定的几何解释。让我们看看另一个例子来验证通用的算法逻辑。
示例 2：
输入矩阵 arr[][] 为：
{
{1, 4, 3, 1, 3, 2},
{3, 2, 1, 3, 2, 4},
{2, 3, 3, 2, 3, 1}
}
输出： 4
这个例子中，中间明显有一个凹陷区域。中间高度为 1 的单元格被高度为 3, 2, 3 等的单元格包围。外围有一圈高度较高的单元格（如 3, 4, 2…），水被锁在这个“碗”里。
解题思路：为什么需要优先队列？
我们如何系统地解决这个问题呢？这里我们将使用一种非常高效的贪心算法结合优先队列（最小堆）。
#### 核心逻辑：
我们可以把这个问题想象成往地图里注水。水是从哪里开始确定的？是从边界开始的。
- 确定水位：整个矩阵的水位上限，是由矩阵边界上最低的那个单元格决定的。就像一个水池，如果最边缘的挡板最低，水满了就会从那里溢出，内部水位永远不会超过这个最低边缘的高度（除非内部有更高的墙挡住，但我们需要从外向内收缩）。
- 由外向内收缩：
* 首先，我们将所有边界单元格放入最小堆中，并标记为已访问。这些是当前的“海岸线”。
* 我们记录当前已探索区域中的最大水位高度 max_height（初始为最小堆顶部的元素高度）。
* 每次我们从堆中取出高度最低的单元格 current。
* 然后检查它的所有邻居（内部未访问的单元格）。
* 关键判断：如果邻居的高度 INLINECODE7370235c 小于 当前的 INLINECODE1c8c64ca，说明这个邻居地势低洼，水可以流进来并保留。积水量就是 INLINECODE0df5348b。我们将该邻居的水位视为 INLINECODEf40ca29d（即填充后的高度），并将其放入堆中，因为它现在成了新的边界（水位线）。
* 如果邻居的高度 大于或等于 INLINECODE7a67104f，说明这里地势高，水存不住。我们更新 INLINECODEa2b5dea0，并将这个邻居放入堆中作为新的硬边界。
- 为什么这样做是对的？
因为我们总是从当前最低的边界开始处理。这保证了如果当前的最低边界都无法挡住水（即邻居比它还低），那么水肯定会从更低的边界流走。只有当邻居比当前维持的水位线低时，水才能被截留住。这种方法确保了我们是按照“木桶最短木板”的原理来一层层向上计算的。
算法实现与代码详解
让我们用 C++ 来实现上述逻辑。我们将使用 STL 中的 priority_queue 来模拟最小堆（通过自定义比较器）。
#### 1. 数据结构定义
首先，我们需要定义方向数组（用于遍历上下左右）和一个节点结构体来存储单元格信息。
// 定义四个方向：上、右、下、左
int dir[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
// 定义节点结构体，存储坐标和高度
struct Node {
int height;
int x, y;
};
#### 2. 自定义比较器
默认的 priority_queue 是最大堆，我们需要将其改为最小堆，让高度最低的单元格排在队首。
// 自定义比较器，用于构建最小堆
struct Compare {
bool operator()(const Node& a, const Node& b) {
// 返回 true 表示 a 的优先级低于 b
// 这里我们将高度低的放在堆顶，所以逻辑是 height大的优先级低
return a.height > b.height;
}
};
#### 3. 核心函数实现
这是解决该问题的主函数。请仔细阅读代码中的注释，理解每一步的操作。
#include
using namespace std;
// 计算矩阵能截留的雨水总量
int trapRainWater(vector<vector>& heightMap) {
if (heightMap.empty()) return 0;
int M = heightMap.size(); // 行数
int N = heightMap[0].size(); // 列数
// 如果矩阵太小，无法形成闭合区域，直接返回0
if (M < 3 || N < 3) return 0;
// 访问标记矩阵，防止重复遍历
vector<vector> visited(M, vector(N, false));
// 定义最小堆
priority_queue<Node, vector, Compare> pq;
// 步骤 1: 将所有边界单元格加入堆中
for (int i = 0; i < M; ++i) {
for (int j = 0; j < N; ++j) {
// 判断是否为边界：第一行、最后一行、第一列、最后一列
if (i == 0 || i == M - 1 || j == 0 || j == N - 1) {
visited[i][j] = true;
pq.push({heightMap[i][j], i, j});
}
}
}
int ans = 0; // 最终结果：总积水量
int max_height = 0; // 当前边界中的最大高度（即当前水位线）
// 步骤 2: 开始由外向内遍历
while (!pq.empty()) {
// 取出当前高度最低的边界单元格
Node front = pq.top();
pq.pop();
// 更新当前水位线（木桶效应：水位取决于最高的那个边界高度）
// 注意：实际上 max_height 应该记录的是我们遇到的“边界高度”的最大值
// 因为只有当内部比这个边界矮时，才能存水
max_height = max(max_height, front.height);
// 遍历当前单元格的四个邻居
for (int i = 0; i = 0 && nx = 0 && ny < N && !visited[nx][ny]) {
visited[nx][ny] = true; // 标记为已访问
// 步骤 3: 计算积水量
// 如果邻居的高度小于当前水位线，说明这里能存水
if (heightMap[nx][ny] = 水位线，说明这里是个硬挡板，水存不住
// 直接把它加入堆中，更新潜在的水位线
pq.push({heightMap[nx][ny], nx, ny});
}
}
}
}
return ans;
}
代码深度剖析
你可能会问，为什么我们在 INLINECODE55c1bf6b 分支里，推入堆的高度是 INLINECODEfdf3008d 而不是原本的高度？
这是一个非常微妙的点。
- 物理意义：当我们确定一个低洼处 (nx, ny) 的高度为 INLINECODEe5ec2340，而它周围目前的“围墙”高度（即 INLINECODE21345cd5）为 INLINECODE27373c2c，那么这里的水位就会上升到 INLINECODE9f0acb11。对于该单元格的内部邻居来说，它们现在面对的边界高度是 INLINECODEb3f1849a（水面），而不是之前的 INLINECODEb9478b60。所以我们用
H来代表该单元格处理后的状态。 - 贪心保证：这样做保证了堆中始终维护的是当前的“水位边界线”。无论底部的地形（INLINECODE945a03ea）如何，水一旦填满，表面就是平的（INLINECODEd46055f7）。
复杂度分析
时间复杂度：O(M N log(M N))。
* 最坏情况下，我们需要将矩阵中的每一个单元格都放入优先队列中。
每次插入和删除操作的时间复杂度是 O(log K)，其中 K 是堆的大小，最大为 M N。
因此总复杂度为 M N log(M N)。
空间复杂度：O(M N)。
* 我们需要一个 visited 矩阵来标记访问状态。
优先队列 pq 在最坏情况下也需要存储 M N 个节点。
实战技巧与常见误区
在实现这个算法时，有几个常见的陷阱需要特别注意：
- 初始边界的选择：一定要将所有的边界单元格（第一行、最后一行、第一列、最后一列）都放入堆中并标记为已访问。如果漏掉了任何一个，水就会从那个缺口“漏出去”，导致计算结果偏小。
- 堆的类型：务必使用最小堆。如果我们错误地使用了最大堆，算法就会变成“找最高的墙”，这不符合水往低处流的物理规律，会导致逻辑错误。在 C++ 中，默认 INLINECODE294ccb75 是最大堆，必须自定义 INLINECODE7ed2e264 来反转排序逻辑。
- 访问标记：在将单元格推入堆的同时（或者在弹出时处理前，推荐在推入时）必须将其标记为
visited。如果不及时标记，同一个单元格可能会被多次加入堆中（被它的不同邻居加入），导致死循环或内存溢出。 - 数据类型的溢出：虽然题目中通常使用 INLINECODE0c3128db，但在极端情况下（如 200×200 的矩阵，高度差极大），积水量可能会很大。不过在大多数面试和 OJ 平台中，INLINECODE3dab5404 通常足够。如果在工程应用中处理海量地理数据，建议使用 INLINECODE00fb20a7 来存储 INLINECODE1d983020。
总结与进阶
通过这篇文章，我们不仅解决了“二维矩阵接雨水”这个问题，更重要的是学习了如何将物理现象（水往低处流）转化为抽象的算法模型（优先队列 + BFS）。这种从边界向内部收缩的技巧（有时被称为“最外层最小边界优先”）在处理诸如“迷宫最短路径”、“地图包裹区域”等图论问题时也非常有用。
你可以尝试扩展这个问题：如果雨水不仅可以从四周流出，矩阵中间还有几个“排水口”（高度为负数的单元格），算法应该如何调整？答案很简单：在初始化堆时，将中间这些排水口也一并放入堆中即可，算法的主体逻辑无需改动，这就是优秀算法设计的鲁棒性所在。
希望这篇详细的解析能帮助你彻底掌握这个算法。继续保持好奇心，去探索更多有趣的算法世界吧！