2D接雨水

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

问题描述

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

示例

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

输出: 4

解题思路

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

代码实现

import heapq

def trapRainWater(heightMap):
    if not heightMap:
        return 0
    
    m, n = len(heightMap), len(heightMap[0])
    if m < 3 or n < 3:
        return 0
    
    heap = []
    visited = [[False] * n for _ in range(m)]
    
    # 将最外层的单元格加入堆
    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[i][j], i, j))
                visited[i][j] = True
    
    water = 0
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    while heap:
        h, x, y = heapq.heappop(heap)
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < m and 0 <= ny < n and not visited[nx][ny]:
                if heightMap[nx][ny] < h:
                    water += h - heightMap[nx][ny]
                    heightMap[nx][ny] = h
                visited[nx][ny] = True
                heapq.heappush(heap, (heightMap[nx][ny], nx, ny))
    
    return water

# 示例
heightMap = [
  [1, 4, 3, 1, 3, 2],
  [3, 2, 1, 3, 2, 4],
  [2, 3, 3, 2, 3, 1]
]
print(trapRainWater(heightMap))  # 输出: 4

复杂度分析

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

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