LeetCode 407 接雨水 II（3D 版）：python3 题解

目录

• 1. 题目理解
  
• 2. 解题思路与核心思想
  
  
  
  • 2.1 为什么不能用一维接雨水的思路？
    
  • 2.2 优先队列（最小堆）+ 广度优先搜索 (BFS)【⭐】
    
  
  
• 3. 代码实现 (Python 3)
  
• 4. 复杂度分析
  
• 5. 其他解法思路讨论
  
  
  
  • 5.1 二分答案 + BFS/DFS 验证
    
  • 5.2 并查集 (Union-Find)
    
  • 5.3 为什么普通 BFS/DFS 不行？
    
  
  
• 6. 总结
  

1. 题目理解

问题描述：
给定一个 \(m \times n\) 的二维矩阵 heightMap，每个单元格代表一个地形的高度。假设下雨后水能填充在地形的低洼处，请计算这个三维地形最多能接住多少体积的雨水。
核心规则：

• 水可以向上下左右四个方向流动。
  
• 水会从矩阵的边界流出。这意味着边界上的单元格无法接住雨水（除非边界本身围成了一个更高的圈，但在本题定义中，矩阵最外圈视为与外界连通，水会流走）。
  
• 一个内部单元格能接多少水，取决于它周围“围墙”的最低高度。这就像木桶效应：一个木桶能装多少水，取决于最短的那块木板。在二维矩阵中，这个“最短木板”是指从该单元格出发到达边界的所有路径中，路径上最大高度的最小值。
  

示例分析：

1. 输入：heightMap = [
2.   [1,4,3,1,3,2],
3.   [3,2,1,3,2,4],
4.   [2,3,3,2,3,1]
5. ]

复制代码

想象这是一个微缩的地形模型。最外圈是边界，水会从这里流走。内部低洼的地方（比如高度为 1 或 2 的地方）如果被周围高度为 3 或 4 的地方包围，水就会积存下来。积存的高度上限是包围它的最低墙壁高度。
2. 解题思路与核心思想

2.1 为什么不能用一维接雨水的思路？

在一维接雨水（LeetCode 42）中，我们只需要关注左边最高和右边最高。但在二维中，水有四个流动方向。如果我们简单地用 DFS 或 BFS 从内向外或从外向内遍历，无法保证处理顺序的正确性。

• 错误思路：如果先处理了一个高度为 10 的边界，认为内部水位限制是 10，但后来发现旁边还有一个高度为 3 的边界，水其实会从 3 的地方流走。
  
• 正确思路：水总是从最低的缺口流出。因此，我们应该优先处理高度最低的边界单元格，逐步向内收缩。
  

2.2 优先队列（最小堆）+ 广度优先搜索 (BFS)【⭐】

这是本题的最优解法，类似于 Dijkstra 算法求最短路径的思想。
算法流程：

• 初始化边界：将矩阵最外圈的所有单元格放入一个最小堆（Priority Queue）中。堆中存储 (高度，行坐标，列坐标)。同时，将这些单元格标记为 visited（已访问），因为水是从这里开始“渗入”或“流出”的起点。
  
• 维护当前水位线：从堆中弹出高度最小的单元格 (h, r, c)。这个 h 代表了当前包围内部区域的“最低围墙高度”。
  
• 探索邻居：检查该单元格的上下左右四个邻居。
  
  
  
  • 如果邻居未访问过：
    
    
    
    • 情况 A（邻居更低）：如果邻居的高度 neighbor_h < h，说明水可以积存在这里。积水量为 h - neighbor_h。对于更内部的单元格来说，这个位置被水填满后，其有效高度变成了 h（因为水面是平的）。
      
    • 情况 B（邻居更高）：如果邻居的高度 neighbor_h >= h，说明这里不能积水，它成为了新的、更高的围墙。对于更内部的单元格，其有效高度限制变成了 neighbor_h。
      
    • 入堆：无论哪种情况，都将邻居放入堆中，其入堆高度为 max(h, neighbor_h)（即有效高度），并标记为已访问。
      
    
    
  
  
• 重复：重复步骤 2-3，直到堆为空。所有内部单元格都被访问过后，累加的积水量即为答案。
  

3. 代码实现 (Python 3)

[code]from typing import Listimport heapqclass Solution:    def trapRainWater(self, heightMap: List[List[int]]) -> int:        # 获取矩阵的行数和列数        if not heightMap or not heightMap[0]:            return 0                m, n = len(heightMap), len(heightMap[0])                # 如果行数或列数小于 3，中间没有空间可以接水，直接返回 0        # 因为接水至少需要周围有一圈包围，3x3 是最小的可能接水矩阵（中间 1 个格子）        if m < 3 or n < 3:            return 0                # visited 矩阵用于记录哪些单元格已经处理过（加入过堆）        visited = [[False] * n for _ in range(m)]                # 最小堆，存储元组 (高度，行，列)        # Python 的 heapq 默认是最小堆，符合我们需要优先处理最低边界的需求        heap = []                # 1. 初始化：将所有边界单元格加入堆，并标记为已访问        for i in range(m):            for j in range(n):                # 判断是否在边界上：第一行、最后一行、第一列、最后一列                if i == 0 or i == m - 1 or j == 0 or j == n - 1:                    heapq.heappush(heap, (heightMap[j], i, j))                    visited[j] = True                # 记录总接水量        total_water = 0                # 定义四个方向：上、下、左、右        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]                # 2. 开始 BFS 遍历，每次取出当前边界高度最低的点        while heap:            # 弹出高度最小的单元格            height, r, c = heapq.heappop(heap)                        # 遍历该单元格的四个邻居            for dr, dc in directions:                nr, nc = r + dr, c + dc                                # 检查邻居是否在矩阵范围内 且 未被访问过                if 0