題目與適用場景
給定長度為 n 的非負整數陣列 height，height[i] 表示第 i 根寬度為 1 的柱子高度。 計算這些柱子下雨後能接住的總水量。例如：
height = [4, 2, 0, 3, 2, 5]
結果 = 9目標是 O(n) 時間和 O(1) 額外空間。標準限制為 1 <= n <= 20000、 0 <= height[i] <= 100000；輸入不含負高度，也不要求回傳每一欄的水量。
這道題有直接的公開面試證據：2025 年 6 月的一篇百度 Go 後端實習面經把「接雨水」記錄為三道 現場手寫題之一；另一份公開電話面試記錄還追加了「從指定位置倒入有限水量」的變體。力扣中英文 題目把它標為困難題，並同時列出陣列、雙指標、動態規劃、堆疊和單調堆疊等標籤。核心考查是從局部 公式推導線性演算法並證明指標移動，因此分類為 coding，與實作語言和職位方向無關。
面試官考察點
第一，能否先寫出每一欄的正確水量。第 i 欄能達到的水面由左側最高柱和右側最高柱中較矮的 一根決定，不是由相鄰柱決定。若 leftMax[i] 與 rightMax[i] 都包含目前位置，則該欄水量是 min(leftMax[i], rightMax[i]) - height[i]。
第二，能否把前後綴陣列壓縮為常數空間。儲存所有位置的左右最高值很容易得到 O(n) 時間， 雙指標進一步利用「較矮的已知邊界已經足以確定一側答案」，每輪只結算一欄。
第三，是否真正理解移動規則。只背誦「移動較矮指標」不夠；強回答會給出不變量，並分別討論目前 柱子更新邊界和不更新邊界的情況，證明尚未掃描區域不會改變剛結算的水量。
最後，能否準確比較替代方案。前後綴陣列最容易解釋；單調堆疊按凹槽橫向結算，適合相關堆疊題； 雙指標最省空間。三種方法都可以是正確答案，但複雜度、證明方式和擴充能力不同。
回答前需要釐清的問題
- 柱子寬度都為 1 嗎？ 是；若寬度不同，每欄的水深還要乘以對應寬度。
- 高度是否保證非負？ 是；負高度沒有約定的物理含義，不能默默當成更深的坑。
- 空陣列是否允許？ 標準限制不允許；本文實作對空陣列自然回傳
0，但介面契約仍應明確。 - 回傳總量還是逐欄結果？ 主問題只回傳總量；逐欄結果需要輸出陣列，因此空間至少為
O(n)。 - 是否必須達到常數額外空間？ 是；否則前後綴陣列是更容易講清楚的線性方案。
- 數值型別會溢位嗎？ 應按真實限制估算上界；限制變化或使用較窄整數型別時要改用更寬累加器。
- 輸入是一維高度圖還是二維網格？ 本題是一維；二維接雨水需要從外邊界向內擴展，演算法不同。
- 是否允許修改輸入？ 不需要，示範實作只讀取
height。
30 秒回答框架
「某欄的水量等於左右最高柱較小值減去本欄高度。前後綴陣列能在線性時間算出所有左右最高值， 但要 O(n) 空間。我用左右指標、leftMax 和 rightMax 壓縮空間：它們分別記錄已經掃描過的 左側和右側最高值。若 leftMax <= rightMax，右側已知邊界已經不低於 leftMax；左指標目前柱 若不更新左界，水量就確定為 leftMax - height[left]，若更新左界則水量為零。然後左指標右移； 另一側完全對稱。每欄只處理一次，所以時間 O(n)、額外空間 O(1)。」
分步深入解答
第一步：先定義逐欄答案。
令：
L[i] = max(height[0..i])
R[i] = max(height[i..n-1])
water[i] = min(L[i], R[i]) - height[i]因為 L[i] 和 R[i] 都包含 height[i]，兩者都不會小於目前高度，所以公式不需要額外取零。 總水量是所有 water[i] 的總和。這個公式也解釋了為什麼只看左右相鄰柱會失敗：遠處更高的邊界 可能決定整個凹槽的水面。
第二步：用基礎方案建立正確基準。
| 方案 | 時間 | 額外空間 | 特點 | |---|---:|---:|---| | 每欄向兩側掃描最高值 | O(n^2) | O(1) | 公式直接，但重複掃描 | | 前後綴最高值陣列 | O(n) | O(n) | 最容易實作和證明 | | 單調遞減堆疊 | O(n) | O(n) | 按凹槽橫向結算寬度和深度 | | 雙指標 | O(n) | O(1) | 每輪確定一側的一欄 |
前後綴方案先從左到右建立 L，再從右到左建立 R，最後套公式。雙指標不是換了一套水量 定義，只是在尚未儲存完整 L、R 時，利用已經足夠的邊界提前結算。
第三步：建立迴圈不變量。
每輪開始時維護：
left左側的所有位置已經按逐欄公式正確結算。right右側的所有位置已經正確結算。leftMax是已掃描左區間height[0..left-1]的最大值；空區間取0。rightMax是已掃描右區間height[right+1..n-1]的最大值；空區間取0。water是所有已結算位置的水量總和。
未處理區間始終是 [left, right]。每輪必須證明其中至少有一端可以永久結算，隨後縮小這個區間。
第四步：證明為什麼可以移動較小邊界的一側。
若 leftMax <= rightMax，考慮 height[left]：
- 若目前柱高於
leftMax，更新後它成為新的左側最高柱。該欄的左邊界就是自身，水量為0。 - 若目前柱不高於
leftMax，真實右側最高值至少為已經見到的rightMax，而
rightMax >= leftMax。因此左右邊界較小值確定為 leftMax，該欄水量正好是 leftMax - height[left]。
兩種情況都不需要知道未掃描中間區域的具體形狀，所以左欄可以永久結算。若 leftMax > rightMax，對右欄做完全對稱的推理。這個證明也說明比較的是已知最高邊界，不是簡單 比較兩個相鄰柱或隨意猜測哪邊更低。
第五步：實作雙指標。
def trap(height: list[int]) -> int:
left = 0
right = len(height) - 1
left_max = 0
right_max = 0
water = 0
while left <= right:
if left_max <= right_max:
left_max = max(left_max, height[left])
water += left_max - height[left]
left += 1
else:
right_max = max(right_max, height[right])
water += right_max - height[right]
right -= 1
return water迴圈使用 left <= right，確保指標相遇時最後一欄也會結算。先更新目前側最高值再累加，既能讓 新最高柱貢獻零，也能保證差值非負。空陣列時 right = -1，迴圈不執行並回傳 0。
第六步：走查 [4, 2, 0, 3, 2, 5]。
處理位置 目前高度 結算側 更新後邊界 新增水量 累計
0 4 左 leftMax=4 0 0
5 5 右 rightMax=5 0 0
1 2 左 leftMax=4 2 2
2 0 左 leftMax=4 4 6
3 3 左 leftMax=4 1 7
4 2 左 leftMax=4 2 9右邊的高度 5 為左側剩餘各欄提供了足夠高的已知邊界，所以後續連續結算左側。每欄只出現一次， 不會按凹槽重複計水。
第七步：證明終止、正確性與複雜度。
初始化時兩側已處理區間都為空，不變量成立。第四步證明每輪新增的一欄按逐欄公式結算正確，且 更新後的 leftMax 或 rightMax 滿足下一輪定義。每輪至少讓 left 增加一或讓 right 減少一， 所以有限步後 left > right；此時所有位置都已正確結算，總和正確。
每個位置只被存取一次，時間複雜度為 O(n)。除指標、兩個邊界和累加器外不配置隨輸入增長的 儲存，額外空間為 O(1)。
第八步：用公式 oracle 和邊界案例驗證。
固定案例至少涵蓋：單柱、兩柱、全零、嚴格遞增、嚴格遞減、全等高、多個獨立凹槽、平底凹槽、 標準範例，以及 [3, 0, 3]。最後一個案例能發現把迴圈誤寫成 left < right 而漏算相遇位置的錯誤。
再對短隨機非負陣列建立前後綴 L、R，用逐欄公式作為 oracle，與雙指標結果比較。同時檢查結果 非負、鏡像陣列的總水量相同、在陣列兩端加入高度為零的柱子不改變原有總水量。隨機差分用於發現 實作錯誤，正確性仍由不變量證明承擔。
高品質示範回答
「我先把問題變成逐欄計算：位置 i 的水深是 min(max(height[0..i]), max(height[i..n-1])) - height[i]。儲存兩個前後綴陣列能做到 O(n) 時間和 O(n) 空間；若要求常數空間，我會用雙指標。
迴圈中，leftMax 和 rightMax 分別記錄指標外側已經掃描過的最高柱。若 leftMax <= rightMax，我結算左指標：目前柱若更新左界，水量為零；否則右側已有的 rightMax 已經不低於左界，所以未知中間區域不可能把較小邊界降到 leftMax 以下，該欄水量確定 為 leftMax - height[left]。然後左指標右移。另一側完全對稱。
每輪永久處理一欄，終止時所有欄都被處理，因此總時間 O(n)；只儲存常數個變數，額外空間 O(1)。我會測試空或短輸入、單調陣列、等高陣列、多個凹槽和 [3, 0, 3]，並用前後綴公式對 隨機小陣列做差分驗證。」
常見錯誤
- 用左右最高值中的較大者減目前高度 → 水會從較矮邊界溢出 → 始終使用兩側最高值的較小者。
- 只比較相鄰柱 → 遠處邊界被忽略 → 先寫出包含整個左右區間的逐欄公式。
- 先累加再更新目前側最高值 → 新最高柱可能產生負水量 → 先更新邊界，再計算非負差值。
- 迴圈寫成
left < right→[3, 0, 3]的中間欄可能未處理 → 讓相遇位置也進入迴圈。 - 移動較大邊界的一側卻不給證明 → 未知另一側可能仍決定較小水面 → 只結算已有另一邊界支撐的較小側。
- 把「盛最多水的容器」公式套進來 →
寬度 × 邊界高會把柱體和多個欄位重複計算 → 本題按每欄水深求和。 - 說雙指標每輪常數時間就結束分析 → 沒有解釋為什麼答案不會被未來邊界改變 → 給出邊界不變量和兩分證明。
- 聲稱單調堆疊空間也是
O(1)→ 嚴格單調輸入可儲存n個下標 → 準確寫為最壞O(n)。 - 只跑一個標準範例 → 相遇、單調和等高邊界未涵蓋 → 加入固定案例和前後綴 oracle。
追問及應對
追問一：為什麼不直接比較 height[left] 和 height[right]？
另一種正確寫法可以比較兩端目前高度，但它需要配套的不變量和更新順序。本文比較 leftMax 與 rightMax，因為它們直接對應逐欄公式中的邊界。不能把一種寫法的比較條件與另一種 寫法的證明混在一起；面試時選擇一套並保持程式碼、口述和證明一致。
追問二：如果要回傳每一欄接住的水量呢？
處理某欄時把增量寫入長度為 n 的結果陣列，再求和或同時累加。時間仍為 O(n)，但輸出本身需要 O(n) 空間。若呼叫方只消費串流結果，還要注意雙指標的結算順序不是從左到右，必須同時回傳下標 或最後重新排序。
追問三：如果高度只能從左到右串流到達呢？
精確答案依賴未來的右邊界，不能在固定記憶體下對每一欄立即定案。可以用單調堆疊儲存尚未閉合的凹槽， 在更高右邊界到達時結算；最壞仍需 O(n) 記憶體。若記憶體有硬上限，就要允許近似、外部儲存或第二遍 掃描，不能繼續承諾原問題的精確常數空間。
追問四：柱子寬度不同怎麼辦？
若第 i 根柱覆蓋獨立寬度 width[i]，邊界高度邏輯不變，該欄體積改為 waterDepth[i] * width[i]。若輸入描述的是不規則橫座標和柱間空隙，則要先明確定義每段橫向區間 的高度；不能直接把相鄰中心點距離當成整根柱寬。
追問五：二維高度網格如何接雨水？
二維單元的水面由整個外邊界約束，兩個方向的指標不夠。常用方案把所有邊界格放入最小堆，每次 取目前最低邊界向內擴展；較低鄰格貢獻高度差，並以兩者較大值作為新的有效邊界。配合存取標記， m × n 網格的時間為 O(mn log(mn))，空間為 O(mn)。
追問六：什麼時候更適合用單調堆疊？
如果追問要求列出每個被左右邊界閉合的凹槽、解釋橫向寬度，或繼續轉到柱狀圖矩形等單調堆疊模式， 堆疊方案更自然。它維護高度單調遞減的下標；遇到更高柱時彈出凹槽底，使用新堆疊頂端和目前柱作為左右 邊界，按「有效寬度 × 新增水層高度」結算。總時間仍為 O(n)，最壞額外空間為 O(n)。