接雨水 II 图解题解

这道题到底在问什么

输入

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

输出

6(四周都是 3,中间四格 1,2,2,1 全被围住,各接到 3 减自身高度的水)

最优解：一步一步想明白

1. 3记住三句话:边界进小根堆、每次取最矮的边界往里看、邻居接水 = max(0, 边界高 减 自身高),然后以 max 抬高后入堆。下面逐帧套它。
2. 4第一步:把整圈边界格都压进小根堆(蓝色=已入堆的边界)。这一圈就是初始的「围墙」,水要漏只能从它们里最矮的地方漏。这里边界全是 3,中间四格还空着(灰)。
3. 5从堆里取出当前最矮的边界 (0,0)、高 3(琥珀)。它四周的格子要么是边界、要么早被访问过,没有新邻居可灌,直接丢弃,继续取下一个。
4. 6从堆里取出当前最矮的边界 (0,3)、高 3(琥珀)。它四周的格子要么是边界、要么早被访问过,没有新邻居可灌,直接丢弃,继续取下一个。
5. 7从堆里取出当前最矮的边界 (1,0)、高 3(琥珀)。看它还没访问的内邻居,水能不能从这里灌进去。
6. 8往右看 (1,1)、高 1(紫),它比墙 3 矮,能接水 = 3 − 1 = 2(蓝水)。累计水量 = 2。再以有效高度 max(3, 1) = 3 把它压回堆,当新边界。
7. 9从堆里取出当前最矮的边界 (1,3)、高 3(琥珀)。看它还没访问的内邻居,水能不能从这里灌进去。
8. 10往左看 (1,2)、高 2(紫),它比墙 3 矮,能接水 = 3 − 2 = 1(蓝水)。累计水量 = 3。再以有效高度 max(3, 2) = 3 把它压回堆,当新边界。
9. 11从堆里取出当前最矮的边界 (2,0)、高 3(琥珀)。看它还没访问的内邻居,水能不能从这里灌进去。
10. 12往右看 (2,1)、高 2(紫),它比墙 3 矮,能接水 = 3 − 2 = 1(蓝水)。累计水量 = 4。再以有效高度 max(3, 2) = 3 把它压回堆,当新边界。
11. 13从堆里取出当前最矮的边界 (2,3)、高 3(琥珀)。看它还没访问的内邻居,水能不能从这里灌进去。
12. 14往左看 (2,2)、高 1(紫),它比墙 3 矮,能接水 = 3 − 1 = 2(蓝水)。累计水量 = 6。再以有效高度 max(3, 1) = 3 把它压回堆,当新边界。
13. 15从堆里取出当前最矮的边界 (3,0)、高 3(琥珀)。它四周的格子要么是边界、要么早被访问过,没有新邻居可灌,直接丢弃,继续取下一个。
14. 16从堆里取出当前最矮的边界 (3,3)、高 3(琥珀)。它四周的格子要么是边界、要么早被访问过,没有新邻居可灌,直接丢弃,继续取下一个。
15. 17从堆里取出当前最矮的边界 (0,1)、高 3(琥珀)。它四周的格子要么是边界、要么早被访问过,没有新邻居可灌,直接丢弃,继续取下一个。
16. 18从堆里取出当前最矮的边界 (3,1)、高 3(琥珀)。它四周的格子要么是边界、要么早被访问过,没有新邻居可灌,直接丢弃,继续取下一个。
17. 19从堆里取出当前最矮的边界 (0,2)、高 3(琥珀)。它四周的格子要么是边界、要么早被访问过,没有新邻居可灌,直接丢弃,继续取下一个。
18. 20从堆里取出当前最矮的边界 (3,2)、高 3(琥珀)。它四周的格子要么是边界、要么早被访问过,没有新邻居可灌,直接丢弃,继续取下一个。
19. 21从堆里取出当前最矮的边界 (1,1)、高 3(琥珀)。它四周的格子要么是边界、要么早被访问过,没有新邻居可灌,直接丢弃,继续取下一个。
20. 22从堆里取出当前最矮的边界 (1,2)、高 3(琥珀)。它四周的格子要么是边界、要么早被访问过,没有新邻居可灌,直接丢弃,继续取下一个。
21. 23从堆里取出当前最矮的边界 (2,1)、高 3(琥珀)。它四周的格子要么是边界、要么早被访问过,没有新邻居可灌,直接丢弃,继续取下一个。
22. 24从堆里取出当前最矮的边界 (2,2)、高 3(琥珀)。它四周的格子要么是边界、要么早被访问过,没有新邻居可灌,直接丢弃,继续取下一个。
23. 25堆空了,所有格子都被访问过(中间四个凹格都蓄上了蓝水)。把每格接到的水加起来:2 + 1 + 1 + 2 = 6。这就是整张图能接的雨水总量。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List
import heapq
class Solution:
    def trapRainWater(self, heightMap: List[List[int]]) -> int:
        m, n = len(heightMap), len(heightMap[0])
        if m < 3 or n < 3:
            return 0
        seen = [[False] * n for _ in range(m)]
        heap = []
        for r in range(m):
            for c in (0, n - 1):
                heapq.heappush(heap, (heightMap[r][c], r, c)); seen[r][c] = True
        for c in range(1, n - 1):
            for r in (0, m - 1):
                heapq.heappush(heap, (heightMap[r][c], r, c)); seen[r][c] = True
        ans = 0
        while heap:
            h, r, c = heapq.heappop(heap)
            for dr, dc in ((1,0),(-1,0),(0,1),(0,-1)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < m and 0 <= nc < n and not seen[nr][nc]:
                    seen[nr][nc] = True
                    ans += max(0, h - heightMap[nr][nc])
                    heapq.heappush(heap, (max(h, heightMap[nr][nc]), nr, nc))
        return ans

#include <queue>
#include <vector>
using namespace std;
class Solution {
public:
    int trapRainWater(vector<vector<int>>& heightMap) {
        int m = heightMap.size(), n = heightMap[0].size();
        if (m < 3 || n < 3) return 0;
        using T = tuple<int,int,int>;
        priority_queue<T, vector<T>, greater<T>> pq;
        vector<vector<int>> seen(m, vector<int>(n));
        for (int r = 0; r < m; ++r) for (int c : {0, n - 1}) { pq.push({heightMap[r][c], r, c}); seen[r][c] = 1; }
        for (int c = 1; c < n - 1; ++c) for (int r : {0, m - 1}) { pq.push({heightMap[r][c], r, c}); seen[r][c] = 1; }
        int ans = 0, dirs[5] = {1,0,-1,0,1};
        while (!pq.empty()) {
            auto [h, r, c] = pq.top(); pq.pop();
            for (int d = 0; d < 4; ++d) {
                int nr = r + dirs[d], nc = c + dirs[d+1];
                if (nr >= 0 && nr < m && nc >= 0 && nc < n && !seen[nr][nc]) {
                    seen[nr][nc] = 1;
                    ans += max(0, h - heightMap[nr][nc]);
                    pq.push({max(h, heightMap[nr][nc]), nr, nc});
                }
            }
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    public int trapRainWater(int[][] heightMap) {
        int m = heightMap.length, n = heightMap[0].length;
        if (m < 3 || n < 3) return 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        boolean[][] seen = new boolean[m][n];
        for (int r = 0; r < m; r++) for (int c : new int[]{0, n - 1}) { pq.offer(new int[]{heightMap[r][c], r, c}); seen[r][c] = true; }
        for (int c = 1; c < n - 1; c++) for (int r : new int[]{0, m - 1}) { pq.offer(new int[]{heightMap[r][c], r, c}); seen[r][c] = true; }
        int ans = 0;
        int[] dirs = {1,0,-1,0,1};
        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            for (int d = 0; d < 4; d++) {
                int nr = cur[1] + dirs[d], nc = cur[2] + dirs[d + 1];
                if (nr >= 0 && nr < m && nc >= 0 && nc < n && !seen[nr][nc]) {
                    seen[nr][nc] = true;
                    ans += Math.max(0, cur[0] - heightMap[nr][nc]);
                    pq.offer(new int[]{Math.max(cur[0], heightMap[nr][nc]), nr, nc});
                }
            }
        }
        return ans;
    }
}

复杂度

面试官可能追问