Hard

题目描述

给你一个 m x n 的整数矩阵 heightMap ，它表示一个二维高程图中每个单元的高度，请计算下雨后能够接多少雨水。

示例 1：

输入: heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]]
输出: 4
解释: 下雨后，水被接在两个小池塘中，分别接了 1 和 3 单位的雨水。
总的接雨水量为 4。

示例 2：

输入: heightMap = [[3,3,3,3,3],[3,2,2,2,3],[3,2,1,2,3],[3,2,2,2,3],[3,3,3,3,3]]
输出: 10

提示：

  • m == heightMap.length
  • n == heightMap[i].length
  • 1 <= m, n <= 200
  • 0 <= heightMap[i][j] <= 2 * 10^4

解题思路

这道题是经典的"接雨水"问题的二维版本。关键思路是从边界开始，逐步向内部扩展，利用优先队列（最小堆）来确保每次处理的都是当前可到达的最低高度。

核心思想：

  1. 水能否被接住取决于四周的最低"挡板"高度
  2. 边界上的格子无法接水，作为起始点
  3. 使用优先队列维护当前可处理的格子，按高度从小到大排序
  4. 对于每个从队列中取出的格子，检查其四个相邻格子
  5. 如果相邻格子的高度小于当前水位，说明可以接水

算法步骤：

  1. 将所有边界格子加入优先队列，并标记为已访问
  2. 从队列中取出高度最小的格子作为当前处理点
  3. 遍历其四个方向的相邻格子
  4. 如果相邻格子未访问过，计算该位置能接的水量
  5. 将相邻格子加入队列，水位高度为 max(当前高度, 相邻格子原始高度)
  6. 重复直到队列为空

这种方法确保了水总是从最低的出口开始"倾倒"，符合物理直觉。

代码实现

class Solution {
public:
    int trapRainWater(vector<vector<int>>& heightMap) {
        int m = heightMap.size(), n = heightMap[0].size();
        if (m <= 2 || n <= 2) return 0;
        
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        
        // 将边界加入优先队列
        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.push({heightMap[i][j], i * n + j});
                    visited[i][j] = true;
                }
            }
        }
        
        int directions[4][2] = {{0,1}, {1,0}, {0,-1}, {-1,0}};
        int result = 0;
        
        while (!pq.empty()) {
            auto [height, pos] = pq.top();
            pq.pop();
            int x = pos / n, y = pos % n;
            
            for (auto& dir : directions) {
                int nx = x + dir[0], ny = y + dir[1];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx][ny]) {
                    result += max(0, height - heightMap[nx][ny]);
                    pq.push({max(height, heightMap[nx][ny]), nx * n + ny});
                    visited[nx][ny] = true;
                }
            }
        }
        
        return result;
    }
};

class Solution:
    def trapRainWater(self, heightMap: List[List[int]]) -> int:
        import heapq
        
        m, n = len(heightMap), len(heightMap[0])
        if m <= 2 or n <= 2:
            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
        
        directions = [(0,1), (1,0), (0,-1), (-1,0)]
        result = 0
        
        while heap:
            height, 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]:
                    result += max(0, height - heightMap[nx][ny])
                    heapq.heappush(heap, (max(height, heightMap[nx][ny]), nx, ny))
                    visited[nx][ny] = True
        
        return result

public class Solution {
    public int TrapRainWater(int[][] heightMap) {
        int m = heightMap.Length, n = heightMap[0].Length;
        if (m <= 2 || n <= 2) return 0;
        
        var pq = new PriorityQueue<(int height, int x, int y), int>();
        var visited = new bool[m, n];
        
        // 将边界加入优先队列
        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.Enqueue((heightMap[i][j], i, j), heightMap[i][j]);
                    visited[i, j] = true;
                }
            }
        }
        
        int[,] directions = {{0,1}, {1,0}, {0,-1}, {-1,0}};
        int result = 0;
        
        while (pq.Count > 0) {
            var (height, x, y) = pq.Dequeue();
            
            for (int d = 0; d < 4; d++) {
                int nx = x + directions[d,0], ny = y + directions[d,1];
                if (nx >= 0 && nx < m && ny >= 0 && ny < n && !visited[nx, ny]) {
                    result += Math.Max(0, height - heightMap[nx][ny]);
                    pq.Enqueue((Math.Max(height, heightMap[nx][ny]), nx, ny), Math.Max(height, heightMap[nx][ny]));
                    visited[nx, ny] = true;
                }
            }
        }
        
        return result;
    }
}

var trapRainWater = function(heightMap) {
    if (!heightMap || heightMap.length === 0 || heightMap[0].length === 0) return 0;
    
    const m = heightMap.length;
    const n = heightMap[0].length;
    const visited = Array(m).fill().map(() => Array(n).fill(false));
    const pq = new MinPriorityQueue({ priority: x => x.height });
    
    // Add all boundary cells to priority queue
    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (i === 0 || i === m - 1 || j === 0 || j === n - 1) {
                pq.enqueue({ row: i, col: j, height: heightMap[i][j] });
                visited[i][j] = true;
            }
        }
    }
    
    const directions = [[0, 1], [0, -1], [1, 0], [-1, 0]];
    let water = 0;
    
    while (!pq.isEmpty()) {
        const { row, col, height } = pq.dequeue().element;
        
        for (const [dr, dc] of directions) {
            const newRow = row + dr;
            const newCol = col + dc;
            
            if (newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && !visited[newRow][newCol]) {
                visited[newRow][newCol] = true;
                const waterLevel = Math.max(height, heightMap[newRow][newCol]);
                water += waterLevel - heightMap[newRow][newCol];
                pq.enqueue({ row: newRow, col: newCol, height: waterLevel });
            }
        }
    }
    
    return water;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(mn log(mn))每个格子最多入队一次，堆操作时间复杂度为 O(log(mn))
空间复杂度O(mn)需要 visited 数组和优先队列存储格子信息

相关题目