LeetCode 407：接雨水 II

LeetCode 407：接雨水 II

问题本质：二维空间的边界约束

与一维接雨水（仅受左右边界限制）不同，二维接雨水的每个位置受四周最低边界的约束。例如，一个单元格能存多少水，取决于周围“最低的墙”——只有当周围存在更低的边界时，水才会被限制在该高度以下。

核心思路：优先队列（最小堆）驱动的边界扩展

关键观察

水的高度由 当前最低的边界 决定。例如，若当前边界的最小高度是 h，则内部所有比 h 低的单元格最多能存 h - height 的水（height 是单元格自身高度）。

算法逻辑

1. 初始化边界：矩阵的外围单元格无法存水（水会流走），因此作为初始边界。
2. 维护最小堆：将边界单元格按高度排序，每次取出 高度最小的边界（因为它是当前最严格的约束）。
3. 扩展边界：遍历当前边界的四个邻居，根据邻居高度与当前边界高度的关系：
   • 若邻居更低：计算存水量（当前边界高度 - 邻居高度），并将邻居以 当前边界高度 加入堆（存水后，该邻居的上表面成为新边界）。
   • 若邻居更高：邻居自身成为新边界，以 自身高度 加入堆。

算法步骤详解

1. 数据结构与初始化

• 优先队列（最小堆）：存储 [高度, 行, 列]，按高度升序排列（确保每次处理最低边界）。
• 访问标记：visited 数组标记单元格是否已处理，避免重复计算。
• 边界初始化：将矩阵的第一行、最后一行、第一列、最后一列加入堆，并标记为已访问。

int m = heightMap.length;int n = heightMap[0].length;boolean[][] visited = new boolean[m][n];PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);// 初始化边界（外围单元格）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) { pq.offer(new int[]{heightMap[i][j], i, j}); visited[i][j] = true; } }}

2. 方向数组与核心循环

定义四个方向（上、下、左、右），遍历当前边界的邻居：

int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; // 四个方向int res = 0;while (!pq.isEmpty()) { int[] curr = pq.poll(); // 取出当前最低边界 int currHeight = curr[0], x = curr[1], y = curr[2]; for (int[] dir : dirs) { int nx = x + dir[0], ny = y + dir[1]; // 邻居坐标 // 检查邻居是否在矩阵内且未被访问 if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny]) { visited[nx][ny] = true; // 标记为已访问 if (heightMap[nx][ny] < currHeight) { // 邻居更低，计算存水量 res += currHeight - heightMap[nx][ny]; // 存水后，邻居的上表面高度为 currHeight（作为新边界） pq.offer(new int[]{currHeight, nx, ny}); } else { // 邻居更高，自身成为新边界 pq.offer(new int[]{heightMap[nx][ny], nx, ny}); } } }}

关键逻辑解析

1. 为什么用最小堆？
   最小堆确保每次处理当前最低的边界。因为低边界是存水的“瓶颈”——只有突破低边界，存水高度才会被更高的边界限制。先处理低边界，能保证存水计算的准确性。

2. 存水的计算条件：
   当邻居高度 < 当前边界高度 时，水会被当前边界“拦住”，存水量为 currHeight - heightMap[nx][ny]。此时，邻居的上表面高度等于当前边界高度（水的高度），因此将其以 currHeight 加入堆，作为新边界。

3. 边界的动态扩展：
   若邻居更高，则它自身成为新的边界（水无法超过它），因此以自身高度加入堆；若邻居更低，则存水后以当前边界高度作为新边界（水的高度由当前边界决定）。

复杂度分析

• 时间复杂度：O(mn log(mn))

  • 每个单元格最多入堆、出堆各一次，堆操作的时间复杂度为 O(log(mn))（堆的最大规模为 mn）。
  • 遍历所有单元格和方向的时间为 O(mn)。

• 空间复杂度：O(mn)

  • visited 数组占用 O(mn) 空间。
  • 优先队列最多存储 mn 个单元格，空间复杂度为 O(mn)。

示例模拟（以题目示例1为例）

输入：

heightMap = [ [1,4,3,1,3,2], [3,2,1,3,2,4], [2,3,3,2,3,1]]

初始化边界（外围单元格）

将第一行、第三行（索引0和2）、第一列、第六列（索引0和5）的单元格加入堆。初始堆中的元素按高度排序，例如 (1,0,0)、(1,0,3)、(2,0,5) 等。

第一次处理堆顶（最小高度，如 (1,0,0)）

• 邻居为 (0,1)（高度4）和 (1,0)（高度3）。
• (0,1) 高度4 > 1，加入堆 [4,0,1]。
• (1,0) 高度3 > 1，加入堆 [3,1,0]。
• 无存水（邻居更高）。

处理下一个堆顶（如 (1,0,3)）

• 邻居为 (0,2)（高度3）、(0,4)（高度3）、(1,3)（高度3）。
• 所有邻居高度 > 1，加入堆，无存水。

处理堆顶 (2,0,5)（高度2）

• 邻居为 (0,4)（高度3，已访问）、(1,5)（高度4）。
• (1,5) 高度4 > 2，加入堆。

后续处理中，当遇到低边界时计算存水

例如，假设堆顶为 (2,1,1)（高度2，来自中间区域），其邻居 (1,2) 高度1 < 2：

• 存水量：2 - 1 = 1，累加到 res。
• 将 (2,1,2) 加入堆（存水后高度为2）。

通过不断扩展边界并计算存水，最终累加得到结果 4（与题目示例一致）。

总结：二维接雨水的本质是“边界约束”

该算法通过 最小堆动态维护最低边界，模拟了水在二维空间中“从最低处开始积累”的过程。核心思想是：水的高度由当前最严格的（最低）边界决定，通过优先处理低边界，确保存水计算的高效与准确。

这种方法不仅解决了二维接雨水问题，还体现了“贪心 + 优先队列”在处理动态边界约束问题中的经典应用，可推广到类似的空间约束问题（如洪水填充、区域扩展等）。

完整代码

import java.util.PriorityQueue;import java.util.Arrays;class Solution { public int trapRainWater(int[][] heightMap) { if (heightMap == null || heightMap.length == 0 || heightMap[0].length == 0) { return 0; } int m = heightMap.length; int n = heightMap[0].length; boolean[][] visited = new boolean[m][n]; // 最小堆：存储 [高度, 行, 列]，按高度升序排列 PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]); // 初始化边界（第一行、最后一行、第一列、最后一列） 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) {  pq.offer(new int[]{heightMap[i][j], i, j});  visited[i][j] = true; } } } // 四个方向：上、下、左、右 int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; int res = 0; while (!pq.isEmpty()) { int[] curr = pq.poll(); int currHeight = curr[0], x = curr[1], y = curr[2]; for (int[] dir : dirs) { int nx = x + dir[0]; int ny = y + dir[1]; // 检查邻居是否在矩阵内且未被访问 if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny]) {  visited[nx][ny] = true;  if (heightMap[nx][ny] < currHeight) { // 邻居高度低于当前边界，可接水：边界高度 - 邻居高度 res += currHeight - heightMap[nx][ny]; // 新边界高度仍为 currHeight（水的高度由当前边界决定） pq.offer(new int[]{currHeight, nx, ny});  } else { // 邻居高度高于当前边界，自身成为新边界 pq.offer(new int[]{heightMap[nx][ny], nx, ny});  } } } } return res; }}