HardRating 2062
42. Trapping Rain Water
arraytwo-pointersdynamic-programmingstackmonotonic-stack
解題說明
Trapping Rain Water
題目描述：
給定一個非負整數陣列 height，其中每個元素代表一根柱子的高度，計算下雨後這些柱子之間能夠蓄積多少單位的雨水。
解題思路：
對於每個位置 i，它能蓄積的水量等於：
water[i] = min(最高左側柱子, 最高右側柱子) - height[i]
（若結果為負，表示無法積水，取 0）
雙指標解法（最優）：
維護兩個指標 left 和 right 從兩端向中間收縮，同時記錄 maxLeft（左側最高柱子）和 maxRight（右側最高柱子）。
核心觀察：
- 若
maxLeft <= maxRight：位置left的積水量由maxLeft決定（因為右側至少有maxRight >= maxLeft，所以瓶頸在左側）。- 更新
maxLeft = max(maxLeft, height[left])。 - 累加
res += maxLeft - height[left]（若height[left] > maxLeft則更新 maxLeft，此時貢獻為 0）。 - 移動
left++。
- 更新
- 若
maxLeft > maxRight：位置right的積水量由maxRight決定，對稱處理right--。
這樣每次處理一個位置，直到 left >= right 為止，一次線性掃描即完成計算。
C++ 解法
複雜度分析
時間複雜度：O(n) — 雙指標從兩端向中間移動，每個元素恰好被處理一次，總迭代次數為 n-1 次。
空間複雜度：O(1) — 只使用了 left、right、maxLeft、maxRight、res 等常數個變數，不需要額外的陣列或資料結構。
虛擬碼
1. Initialize left = 0, right = n - 1, maxLeft = 0, maxRight = 0, res = 0.
2. While left < right:
a. If maxLeft <= maxRight:
- Update maxLeft = max(maxLeft, height[left]).
- Add maxLeft - height[left] to res.
- Increment left.
b. Else:
- Update maxRight = max(maxRight, height[right]).
- Add maxRight - height[right] to res.
- Decrement right.
3. Return res.其他解法
動態規劃（預計算前後最大值）O(n) 時間 O(n) 空間：先用兩個陣列 leftMax[i] 和 rightMax[i] 分別記錄每個位置左側和右側的最大高度，再逐一計算每個位置的積水量。思路最直觀，但需要 O(n) 額外空間。雙指標法本質上是此方法的空間最佳化版本。
單調棧法 O(n) 時間 O(n) 空間：使用一個遞減的單調棧，以「橫向層」的方式計算積水。每當遇到比棧頂更高的柱子，就彈出棧頂並計算以彈出元素為底的一層水量。此方法適合思考「按層計算」的場景，但程式碼相對複雜，且空間複雜度同為 O(n)。
延伸思考
- 雙指標法的正確性依賴於「選擇較小 max 那一側來處理」的策略，請詳細說明為什麼這個貪婪選擇是安全的，即為什麼不會漏算水量？
- 如果問題從二維（柱狀圖）延伸到三維（LeetCode 407 Trapping Rain Water II），原本的雙指標解法無法直接應用，你會如何用優先佇列（priority queue）來處理三維版本？
- 本題與「Largest Rectangle in Histogram（LeetCode 84）」都涉及柱狀結構，它們的核心思路有何異同？