LeetCode 407：接雨水 II-EW帮帮网

LeetCode 407：接雨水 II

在这里插入图片描述

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

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

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

关键观察

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

算法逻辑

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

算法步骤详解

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});
            }
        }
    }
}

关键逻辑解析

为什么用最小堆？
最小堆确保每次处理当前最低的边界。因为低边界是存水的“瓶颈”——只有突破低边界，存水高度才会被更高的边界限制。先处理低边界，能保证存水计算的准确性。
存水的计算条件：
当邻居高度 < 当前边界高度 时，水会被当前边界“拦住”，存水量为 currHeight - heightMap[nx][ny]。此时，邻居的上表面高度等于当前边界高度（水的高度），因此将其以 currHeight 加入堆，作为新边界。
边界的动态扩展：
若邻居更高，则它自身成为新的边界（水无法超过它），因此以自身高度加入堆；若邻居更低，则存水后以当前边界高度作为新边界（水的高度由当前边界决定）。

复杂度分析

时间复杂度：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;
    }
}

LeetCode 407：接雨水 II