題目描述:給定一個 m×n 的高度矩陣 heightMap,代表地形的高度。計算該地形能夠蓄積的雨水總量(三維接雨水問題)。
解題思路(最小堆 + BFS):
三維接雨水的核心洞察:水從最矮的邊界往內「滲透」,每次從最矮的邊界格子出發,探索其內部鄰居能蓄多少水。
初始化:將所有邊界格子(矩陣四條邊上的格子)加入最小堆,格子形式為 (height, row, col),並標記為已訪問。邊界格子無法蓄水(水會直接流出)。
BFS 擴展:每次從堆中取出高度最小的格子 (h, r, c)(目前最脆弱的邊界),探索其四個方向的鄰居 (nr, nc):
h 限制:
heightMap[nr][nc] < h:能蓄水,蓄水量 += h - heightMap[nr][nc],再以高度 h 加入堆(因為水填滿後該位置等效高度為 h)。heightMap[nr][nc] >= h:不能蓄水,以 heightMap[nr][nc] 加入堆,更新邊界。持續直到堆為空,累計蓄水量即為答案。
時間複雜度:O(m·n·log(m·n)) — 共 m·n 個格子,每個格子最多入堆一次,每次堆操作 O(log(m·n)),故整體為 O(m·n·log(m·n))。
空間複雜度:O(m·n) — 堆最多儲存所有格子,visited 陣列大小 m×n,故空間 O(m·n)。
Function trapRainWater(heightMap):
m = rows, n = cols
If m < 3 or n < 3: return 0
// Step 1: Initialize min-heap with all border cells
minHeap = empty min-heap
visited[m][n] = all false
For each border cell (r, c):
Push (heightMap[r][c], r, c) into minHeap
Mark visited[r][c] = true
// Step 2: BFS from minimum boundary outward
water = 0
While minHeap not empty:
(h, r, c) = pop minimum from minHeap
For each neighbor (nr, nc) of (r, c):
If out of bounds or already visited: continue
Mark visited[nr][nc] = true
If heightMap[nr][nc] < h:
water += h - heightMap[nr][nc] // can trap water
Push (h, nr, nc) into minHeap // effective height is h after filling
Else:
Push (heightMap[nr][nc], nr, nc) into minHeap
Return water二維接雨水思路推廣(不適用):一維接雨水使用兩指針或動態規劃,記錄左右最大值。三維情況下邊界是「環狀」的,無法直接套用左右最大值邏輯,因此必須用最小堆模擬「最弱邊界」的概念。
純 BFS 不使用堆(錯誤思路說明):若不按高度排序而直接 BFS,無法確保「先處理最矮邊界」的性質,會導致蓄水計算錯誤。堆在此處的作用是保證每次都從最低的「水牆」開始擴展,這是正確性的關鍵。
Dijkstra 類比:本演算法本質是 Dijkstra 最短路徑的變體——將「最小邊界高度」視為「到邊界的最短距離(即最大可能水位)」,每個格子的水位由通往邊界路徑上的最大高度決定(瓶頸路徑問題)。