接雨水问题是一个经典的算法问题，通常分为一维和二维两种情况。二维接雨水问题（也称为“接雨水 II”）是在一个二维矩阵中计算能够接住的雨水量。每个单元格的高度表示地形的高度，雨水会在低洼处积聚。

问题描述

给定一个 m x n 的矩阵 heightMap，其中每个元素 heightMap[i][j] 表示单元格 (i, j) 的高度。计算这个矩阵能够接住的雨水量。

示例

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

输出: 4

解题思路

1. 边界处理：首先，矩阵的最外层单元格无法接住雨水，因为它们没有完全被包围。
2. 最小堆：使用一个最小堆（优先队列）来存储边界单元格，并按照高度排序。
3. 遍历：从堆中取出最小的单元格，检查其四周的单元格。如果四周的单元格高度小于当前单元格的高度，则可以接住雨水。接住的雨水量为当前单元格高度减去四周单元格的高度。
4. 更新堆：将四周的单元格加入堆中，并更新其高度为当前单元格的高度（因为雨水已经填平了低洼处）。
5. 重复：重复上述步骤，直到堆为空。

代码实现

 1import heapq
 2
 3def trapRainWater(heightMap):
 4    if not heightMap:
 5        return 0
 6    
 7    m, n = len(heightMap), len(heightMap[0])
 8    if m < 3 or n < 3:
 9        return 0
10    
11    heap = []
12    visited = [[False] * n for _ in range(m)]
13    
14    # 将最外层的单元格加入堆
15    for i in range(m):
16        for j in range(n):
17            if i == 0 or i == m - 1 or j == 0 or j == n - 1:
18                heapq.heappush(heap, (heightMap[i][j], i, j))
19                visited[i][j] = True
20    
21    water = 0
22    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
23    
24    while heap:
25        h, x, y = heapq.heappop(heap)
26        for dx, dy in directions:
27            nx, ny = x + dx, y + dy
28            if 0 <= nx < m and 0 <= ny < n and not visited[nx][ny]:
29                if heightMap[nx][ny] < h:
30                    water += h - heightMap[nx][ny]
31                    heightMap[nx][ny] = h
32                visited[nx][ny] = True
33                heapq.heappush(heap, (heightMap[nx][ny], nx, ny))
34    
35    return water
36
37# 示例
38heightMap = [
39  [1, 4, 3, 1, 3, 2],
40  [3, 2, 1, 3, 2, 4],
41  [2, 3, 3, 2, 3, 1]
42]
43print(trapRainWater(heightMap))  # 输出: 4

复杂度分析

• 时间复杂度：O(M * N * log(M + N))，其中 M 和 N 分别是矩阵的行数和列数。每个单元格最多被处理一次，每次处理的时间复杂度为 O(log(M + N))。
• 空间复杂度：O(M * N)，用于存储堆和访问标记。

这个算法通过最小堆和广度优先搜索（BFS）的结合，有效地解决了二维接雨水问题。