LeetCode 407. 接雨水 II

题目描述
给定一个 m x n 的矩阵，其中的值表示高度。矩阵的四个边界被视为被海洋包围。雨水可以从任意单元格流向上下左右四个方向中高度更低或相等的单元格。请计算矩阵中能接多少雨水。

示例
输入：

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

输出：4
解释：雨水会填充到高度为1和2的单元格中，总接水量为4。

解题思路

1. 问题分析

   • 二维接雨水问题需要从边界向内收缩。边界单元格无法蓄水（水会流出），但内部单元格的蓄水高度取决于其周围最低的“屏障”高度。
   • 关键思想：水从边界最低处开始向内渗透，用最小堆（优先队列）动态维护当前边界的最低高度。

2. 算法选择：最小堆 + BFS

   • 将矩阵边界所有单元格加入最小堆（按高度排序），并标记为已访问。
   • 每次取出堆中高度最小的单元格，检查其四个邻居：
     • 如果邻居未访问过，计算其蓄水量（当前边界高度与邻居高度的差值，若差值为正则蓄水）。
     • 将邻居标记为已访问，并以当前边界高度和邻居高度的较大值作为邻居的新高度加入堆中（因为水可能被更高的邻居挡住）。

3. 步骤详解

   • 初始化：
     • 创建最小堆，存储 (高度, 行索引, 列索引)。
     • 创建访问矩阵 visited，标记已处理单元格。
     • 将矩阵四边所有单元格加入堆并标记为已访问。
   • 循环处理堆：
     • 弹出堆顶元素（当前最低边界高度 h）。
     • 遍历其上下左右四个邻居：
       • 若邻居越界或已访问，跳过。
       • 若邻居高度 < h，则蓄水量增加 h - 邻居高度。
       • 将邻居高度更新为 max(h, 邻居高度)（确保水不会从低处漏出），并加入堆中。
   • 终止条件：堆为空时结束。

4. 为什么有效？

   • 最小堆保证始终从最低的边界开始向内注水，避免水从低处泄漏。
   • 每次处理时，邻居的蓄水高度由当前边界高度决定，模拟了水流动的物理过程。

复杂度分析

• 时间复杂度：O(mn log(m+n))，每个单元格入堆一次，堆操作复杂度为对数级。
• 空间复杂度：O(mn)，用于堆和访问矩阵。

通过以上步骤，可以高效计算二维矩阵中的接雨水量。