HardRating 2200

407. Trapping Rain Water II

arraybreadth-first-searchheap-priority-queuematrix

在 LeetCode 上作答 ↗

解題說明

Trapping Rain Water II

題目描述：給定一個 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] 加入堆，更新邊界。
持續直到堆為空，累計蓄水量即為答案。

C++ 解法

複雜度分析

時間複雜度：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 最短路徑的變體——將「最小邊界高度」視為「到邊界的最短距離（即最大可能水位）」，每個格子的水位由通往邊界路徑上的最大高度決定（瓶頸路徑問題）。

延伸思考

本題與一維接雨水（LeetCode 42）的核心思想有何差異？為什麼一維可以用 O(n) 的兩指針，而二維需要 O(mn log mn) 的最小堆？
若地形允許有「洞」（某些格子可以直接穿透），蓄水計算需要如何修改？
如果矩陣非常大（如 1000×1000），有什麼優化策略可以減少常數或改善實際運行時間？

解題說明

Trapping Rain Water II

題目描述：給定一個 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] 加入堆，更新邊界。
持續直到堆為空，累計蓄水量即為答案。

虛擬碼

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

其他解法

延伸思考

本題與一維接雨水（LeetCode 42）的核心思想有何差異？為什麼一維可以用 O(n) 的兩指針，而二維需要 O(mn log mn) 的最小堆？
若地形允許有「洞」（某些格子可以直接穿透），蓄水計算需要如何修改？
如果矩陣非常大（如 1000×1000），有什麼優化策略可以減少常數或改善實際運行時間？