407. 接雨水 II
题目描述
输入一个 m x n 的非负整数矩阵 heightMap。每个格子是底面为 1 x 1 的立柱，数值为它的高度，整体构成一块起伏的地形。
下雨后，水会积在被更高地形围住的低洼处，而能从边界流走的水留不住。
返回整块地形最多能存住的雨水总体积。
示例 1
输入：heightMap = [[1,4,3,1,3,2],[3,2,1,3,2,4],[2,3,3,2,3,1]] 输出：4
解释：中间几处凹陷分别存住 1、2、1 个单位的水，共 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
解释：外圈高 3；内圈 8 个高 2 的格子各存 1，中心高 1 的格子存 2，共 10。
数据范围
m == heightMap.lengthn == heightMap[i].length1 <= m, n <= 2000 <= heightMap[i][j] <= 2 * 10^4
解题思路：最小堆从边界向内扩展
水能不能留住取决于“围墙”中最矮的那一块。先把最外一圈格子放进小根堆当围墙。每次弹出最矮的墙 h，检查它的未访问邻居：邻居比 h 低就能装 h − 高度 的水；然后邻居以 max(h, 自身高度) 的“有效高度”成为新围墙入堆。这样围墙从外向内收缩，每个格子只处理一次。
为什么正确
堆中每个格子的值 = 从外界到达它所需翻越的最低水位；弹出顺序按这个水位从低到高。
复杂度分析
时间 O(mn log(mn))，空间 O(mn)。
易错点
不能像一维那样只看行或列的左右最大值：水会从任意方向绕出去，必须用“最低围墙”从外向内推进；邻居入堆时要用 max(h, 高度)，否则会低估水位。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def trapRainWater(self, heightMap: List[List[int]]) -> int:
m, n = len(heightMap), len(heightMap[0])
seen = [[False] * n for _ in range(m)]
heap = []
for i in range(m):
for j in range(n):
if i == 0 or j == 0 or i == m - 1 or j == n - 1:
heapq.heappush(heap, (heightMap[i][j], i, j))
seen[i][j] = True
water = 0
while heap:
h, i, j = heapq.heappop(heap)
for x, y in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
if 0 <= x < m and 0 <= y < n and not seen[x][y]:
seen[x][y] = True
water += max(0, h - heightMap[x][y])
heapq.heappush(heap, (max(h, heightMap[x][y]), x, y))
return waterclass Solution {
public int trapRainWater(int[][] heightMap) {
int m = heightMap.length, n = heightMap[0].length;
boolean[][] seen = new boolean[m][n];
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 || j == 0 || i == m - 1 || j == n - 1) {
heap.offer(new int[]{heightMap[i][j], i, j});
seen[i][j] = true;
}
}
}
int water = 0;
int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
while (!heap.isEmpty()) {
int[] cur = heap.poll();
int h = cur[0], i = cur[1], j = cur[2];
for (int[] d : dirs) {
int x = i + d[0], y = j + d[1];
if (x >= 0 && x < m && y >= 0 && y < n && !seen[x][y]) {
seen[x][y] = true;
water += Math.max(0, h - heightMap[x][y]);
heap.offer(new int[]{Math.max(h, heightMap[x][y]), x, y});
}
}
}
return water;
}
}class Solution {
public:
int trapRainWater(vector<vector<int>>& heightMap) {
int m = heightMap.size(), n = heightMap[0].size();
vector<vector<bool>> seen(m, vector<bool>(n, false));
priority_queue<array<int, 3>, vector<array<int, 3>>, greater<>> heap;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 || j == 0 || i == m - 1 || j == n - 1) {
heap.push({heightMap[i][j], i, j});
seen[i][j] = true;
}
}
}
int water = 0;
int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
while (!heap.empty()) {
auto [h, i, j] = heap.top();
heap.pop();
for (auto& d : dirs) {
int x = i + d[0], y = j + d[1];
if (x >= 0 && x < m && y >= 0 && y < n && !seen[x][y]) {
seen[x][y] = true;
water += max(0, h - heightMap[x][y]);
heap.push({max(h, heightMap[x][y]), x, y});
}
}
}
return water;
}
};type cellHeap [][3]int
func (h cellHeap) Len() int { return len(h) }
func (h cellHeap) Less(i, j int) bool { return h[i][0] < h[j][0] }
func (h cellHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *cellHeap) Push(v any) { *h = append(*h, v.([3]int)) }
func (h *cellHeap) Pop() any { old := *h; v := old[len(old)-1]; *h = old[:len(old)-1]; return v }
func trapRainWater(heightMap [][]int) int {
m, n := len(heightMap), len(heightMap[0])
seen := make([][]bool, m)
for i := range seen {
seen[i] = make([]bool, n)
}
h := &cellHeap{}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if i == 0 || j == 0 || i == m-1 || j == n-1 {
heap.Push(h, [3]int{heightMap[i][j], i, j})
seen[i][j] = true
}
}
}
water := 0
dirs := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
for h.Len() > 0 {
cur := heap.Pop(h).([3]int)
for _, d := range dirs {
x, y := cur[1]+d[0], cur[2]+d[1]
if x >= 0 && x < m && y >= 0 && y < n && !seen[x][y] {
seen[x][y] = true
if cur[0] > heightMap[x][y] {
water += cur[0] - heightMap[x][y]
}
heap.Push(h, [3]int{max(cur[0], heightMap[x][y]), x, y})
}
}
}
return water
}const heappush = (h, e) => {
h.push(e);
for (let i = h.length - 1, p; i > 0 && h[p = (i - 1) >> 1][0] > h[i][0]; i = p) [h[p], h[i]] = [h[i], h[p]];
};
const heappop = h => {
const top = h[0], last = h.pop();
if (h.length) {
h[0] = last;
for (let i = 0; ;) {
const l = 2 * i + 1, r = l + 1; let s = i;
if (l < h.length && h[l][0] < h[s][0]) s = l;
if (r < h.length && h[r][0] < h[s][0]) s = r;
if (s === i) break;
[h[s], h[i]] = [h[i], h[s]]; i = s;
}
}
return top;
};
var trapRainWater = function(heightMap) {
const m = heightMap.length, n = heightMap[0].length;
const seen = Array.from({ length: m }, () => new Array(n).fill(false));
const heap = [];
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (i === 0 || j === 0 || i === m - 1 || j === n - 1) {
heappush(heap, [heightMap[i][j], i, j]);
seen[i][j] = true;
}
}
}
let water = 0;
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
while (heap.length) {
const [h, i, j] = heappop(heap);
for (const [dx, dy] of dirs) {
const x = i + dx, y = j + dy;
if (x >= 0 && x < m && y >= 0 && y < n && !seen[x][y]) {
seen[x][y] = true;
water += Math.max(0, h - heightMap[x][y]);
heappush(heap, [Math.max(h, heightMap[x][y]), x, y]);
}
}
}
return water;
};const heappush = (h: number[][], e: number[]): void => {
h.push(e);
for (let i = h.length - 1, p; i > 0 && h[p = (i - 1) >> 1][0] > h[i][0]; i = p) [h[p], h[i]] = [h[i], h[p]];
};
const heappop = (h: number[][]): number[] => {
const top = h[0], last = h.pop();
if (h.length) {
h[0] = last;
for (let i = 0; ;) {
const l = 2 * i + 1, r = l + 1; let s = i;
if (l < h.length && h[l][0] < h[s][0]) s = l;
if (r < h.length && h[r][0] < h[s][0]) s = r;
if (s === i) break;
[h[s], h[i]] = [h[i], h[s]]; i = s;
}
}
return top;
};
function trapRainWater(heightMap: number[][]): number {
const m = heightMap.length, n = heightMap[0].length;
const seen = Array.from({ length: m }, () => new Array(n).fill(false));
const heap: number[][] = [];
for (let i = 0; i < m; i++) {
for (let j = 0; j < n; j++) {
if (i === 0 || j === 0 || i === m - 1 || j === n - 1) {
heappush(heap, [heightMap[i][j], i, j]);
seen[i][j] = true;
}
}
}
let water = 0;
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
while (heap.length) {
const [h, i, j] = heappop(heap);
for (const [dx, dy] of dirs) {
const x = i + dx, y = j + dy;
if (x >= 0 && x < m && y >= 0 && y < n && !seen[x][y]) {
seen[x][y] = true;
water += Math.max(0, h - heightMap[x][y]);
heappush(heap, [Math.max(h, heightMap[x][y]), x, y]);
}
}
}
return water;
}其他解法
最小堆每次从最低的边界向内扩展，每个格子只处理一次；广度优先搜索反复松弛水面高度，实现简单但同一格子可能入队多次。
解法 2：广度优先搜索迭代水位 时间 O(m²n²)，空间 O(mn)
设 water[i][j] 为格子接水后的水面高度。边界格子的水面等于自身高度，其余格子先设为整个矩阵的最大高度。从边界格子出发做广度优先搜索：相邻格子的水面高于当前格子水面且高于它自身高度时，把它降到 max(当前水面, 它的高度)，并重新入队。队列为空时水面稳定，答案是所有 water[i][j] - heightMap[i][j] 之和。
不需要堆，思路是不断让水从低处流走直到稳定。一个格子可能被多次更新，最坏复杂度高于堆方法，实际数据上通常也能通过。
from collections import deque
class Solution:
def trapRainWater(self, heightMap):
m, n = len(heightMap), len(heightMap[0])
top = max(max(row) for row in heightMap)
water = [[top] * n for _ in range(m)]
q = deque()
for i in range(m):
for j in range(n):
if i == 0 or j == 0 or i == m - 1 or j == n - 1:
water[i][j] = heightMap[i][j]
q.append((i, j))
while q:
i, j = q.popleft()
for x, y in ((i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1)):
if 0 <= x < m and 0 <= y < n:
if water[x][y] > water[i][j] and water[x][y] > heightMap[x][y]:
water[x][y] = max(water[i][j], heightMap[x][y])
q.append((x, y))
return sum(water[i][j] - heightMap[i][j] for i in range(m) for j in range(n))class Solution {
public int trapRainWater(int[][] heightMap) {
int m = heightMap.length, n = heightMap[0].length;
int top = 0;
for (int[] row : heightMap)
for (int h : row) top = Math.max(top, h);
int[][] water = new int[m][n];
Deque<int[]> q = new ArrayDeque<>();
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++) {
if (i == 0 || j == 0 || i == m - 1 || j == n - 1) {
water[i][j] = heightMap[i][j];
q.offer(new int[]{i, j});
} else {
water[i][j] = top;
}
}
int[][] dirs = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
while (!q.isEmpty()) {
int[] cur = q.poll();
int i = cur[0], j = cur[1];
for (int[] d : dirs) {
int x = i + d[0], y = j + d[1];
if (x >= 0 && x < m && y >= 0 && y < n) {
if (water[x][y] > water[i][j] && water[x][y] > heightMap[x][y]) {
water[x][y] = Math.max(water[i][j], heightMap[x][y]);
q.offer(new int[]{x, y});
}
}
}
}
int res = 0;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++) res += water[i][j] - heightMap[i][j];
return res;
}
}class Solution {
public:
int trapRainWater(vector<vector<int>>& heightMap) {
int m = heightMap.size(), n = heightMap[0].size();
int top = 0;
for (auto& row : heightMap)
for (int h : row) top = max(top, h);
vector<vector<int>> water(m, vector<int>(n, top));
queue<pair<int, int>> q;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++)
if (i == 0 || j == 0 || i == m - 1 || j == n - 1) {
water[i][j] = heightMap[i][j];
q.push({i, j});
}
int dirs[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
while (!q.empty()) {
auto [i, j] = q.front();
q.pop();
for (auto& d : dirs) {
int x = i + d[0], y = j + d[1];
if (x >= 0 && x < m && y >= 0 && y < n) {
if (water[x][y] > water[i][j] && water[x][y] > heightMap[x][y]) {
water[x][y] = max(water[i][j], heightMap[x][y]);
q.push({x, y});
}
}
}
}
int res = 0;
for (int i = 0; i < m; i++)
for (int j = 0; j < n; j++) res += water[i][j] - heightMap[i][j];
return res;
}
};func trapRainWater(heightMap [][]int) int {
m, n := len(heightMap), len(heightMap[0])
top := 0
for _, row := range heightMap {
for _, h := range row {
top = max(top, h)
}
}
water := make([][]int, m)
q := [][2]int{}
for i := 0; i < m; i++ {
water[i] = make([]int, n)
for j := 0; j < n; j++ {
if i == 0 || j == 0 || i == m-1 || j == n-1 {
water[i][j] = heightMap[i][j]
q = append(q, [2]int{i, j})
} else {
water[i][j] = top
}
}
}
dirs := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
for head := 0; head < len(q); head++ {
i, j := q[head][0], q[head][1]
for _, d := range dirs {
x, y := i+d[0], j+d[1]
if x >= 0 && x < m && y >= 0 && y < n {
if water[x][y] > water[i][j] && water[x][y] > heightMap[x][y] {
water[x][y] = max(water[i][j], heightMap[x][y])
q = append(q, [2]int{x, y})
}
}
}
}
res := 0
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
res += water[i][j] - heightMap[i][j]
}
}
return res
}var trapRainWater = function(heightMap) {
const m = heightMap.length, n = heightMap[0].length;
let top = 0;
for (const row of heightMap)
for (const h of row) top = Math.max(top, h);
const water = Array.from({ length: m }, () => new Array(n).fill(top));
const q = [];
for (let i = 0; i < m; i++)
for (let j = 0; j < n; j++)
if (i === 0 || j === 0 || i === m - 1 || j === n - 1) {
water[i][j] = heightMap[i][j];
q.push([i, j]);
}
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
for (let head = 0; head < q.length; head++) {
const [i, j] = q[head];
for (const [dx, dy] of dirs) {
const x = i + dx, y = j + dy;
if (x >= 0 && x < m && y >= 0 && y < n) {
if (water[x][y] > water[i][j] && water[x][y] > heightMap[x][y]) {
water[x][y] = Math.max(water[i][j], heightMap[x][y]);
q.push([x, y]);
}
}
}
}
let res = 0;
for (let i = 0; i < m; i++)
for (let j = 0; j < n; j++) res += water[i][j] - heightMap[i][j];
return res;
};function trapRainWater(heightMap: number[][]): number {
const m = heightMap.length, n = heightMap[0].length;
let top = 0;
for (const row of heightMap)
for (const h of row) top = Math.max(top, h);
const water: number[][] = Array.from({ length: m }, () => new Array<number>(n).fill(top));
const q: number[][] = [];
for (let i = 0; i < m; i++)
for (let j = 0; j < n; j++)
if (i === 0 || j === 0 || i === m - 1 || j === n - 1) {
water[i][j] = heightMap[i][j];
q.push([i, j]);
}
const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
for (let head = 0; head < q.length; head++) {
const [i, j] = q[head];
for (const [dx, dy] of dirs) {
const x = i + dx, y = j + dy;
if (x >= 0 && x < m && y >= 0 && y < n) {
if (water[x][y] > water[i][j] && water[x][y] > heightMap[x][y]) {
water[x][y] = Math.max(water[i][j], heightMap[x][y]);
q.push([x, y]);
}
}
}
}
let res = 0;
for (let i = 0; i < m; i++)
for (let j = 0; j < n; j++) res += water[i][j] - heightMap[i][j];
return res;
}