---
title: "42. Trapping Rain Water"
url: "https://laigary.com/interview/coding/42-trapping-rain-water"
type: "note"
section: "coding"
date: "2023-01-29"
updated: "2026-07-25"
tags: ["Two Pointers", "Classic"]
---

# 42. Trapping Rain Water

[42\. Trapping Rain Water](https://leetcode.com/problems/trapping-rain-water/)

要寫這一題之前，要先了解 [11\. Container With Most Water](/interview/coding/11-container-with-most-water) 的概念。這一題比較特別，題目給定的陣列像是表達一個等高線圖，其中這個等高線內就會有山谷，有山谷的地方就能儲存水，我們要求出總共能夠有多少水被儲存在這個山谷。

## 思路

### 什麼情況才能裝水

先了解這個題目給的所有條件，那就是如果說今天給定的等高線圖，如果只有兩個點，這樣是沒有辦法儲存任何水的，山谷能有的最多水要被包在兩側的山峰內。如果只有一邊有高峰，那水都會流走。

也就是說最少要有類似 `[1, 0, 1]` 這樣的情況才能有水。

接著分析比較複雜一點的情況，像是 `[1, 0, 2, 1, 3]` 這樣的話，在位置 0 到 2 之間，其山谷是 `[1, 0, 2]`，這和之前水桶的問題一樣，最多只能儲存一單位的水，下一個儲存水的地方是 `[2, 1, 3]`，不過這裡最多也只能儲存一單位的水。所以題目的答案就是 2。

下一個例子，`[1, 0, 2, 1, 1, 1, 1, 1, 3]` 這樣的情況的話，第一個部分和上面一樣，但是右邊第二個部分就會有點不好算了，因為我們要不斷的找到右邊界，才能知道能裝多少水。

這個例子還算好處理的，如果上面的這個例子稍微修改一點點，`[1, 0, 2, 1, 0, 1, 0, 1, 3]` 這樣就不能單純的只找右邊的高點了，因為中間有更深的山谷，會可以儲存更多的水；又或是 `[1, 0, 2, 1, 1, 1, 1, 1, 1]` 這樣的例子，其實右邊只是一塊平地，根本不能裝水。

### 想過遞迴，但行不通

其實到這裡，我有想過該不會是要透過遞迴來處理？把大問題慢慢分解成小問題來處理？可是如果每次遞迴時傳一個子陣列進去，**子陣列會不知道上層問題的兩側高度**，可能會造成在子問題中看起來儲存不了水，但是實際上可以的，這樣就會漏算面積。這個「要怎麼判斷儲存水量」的方法，就是這題最困難的地方。

這個死路其實給了很重要的提示：**每一格能裝多少水，是被它以外的資訊決定的。** 所以不要按區塊拆，要按格子算。

### 每一格能裝多少：`min(maxLeft, maxRight) - height[i]`

回到一開始 `[1, 0, 1]` 的例子。如果說我們現在正在座標為 1 的時候，如果說我們知道哪些資訊，就可以確定那個位置可以裝水？這個比較好想，那就是在他的右手邊，一定有一個座標的高度比他高，在他的左手邊，也一定有一個座標的高度比他高。

像是更複雜的例子，`[1, 0, 2, 1, 1, 1, 1, 1, 3]` 在座標 `3 ~ 7` 的山谷中，我們也都知道左邊有座標比他們都高，右邊也有座標比他們都高，因此這樣也就能確定那邊一定可以裝水。

有了這個想法後，可以再回到 `[1, 0, 2, 1, 3]` 的例子，座標 `1` 和 `3` 都可以裝水，雖然一個高度是 `0`，一個高度是 `1`，但是能裝的水容量都一樣是 `1`，因為他們那一個格子的容量，都被兩邊高度的最小值給決定了。於是每一格的水量就是：

```text
water[i] = min(maxHeightFromLeft, maxHeightFromRight) - height[i]
```

答案就是把每一格加起來。**問題從「找出所有山谷」變成「對每一格算一個數字」** —— 這就是遞迴那條死路換來的收穫。

### 為什麼要記「跑動最大值」而不是鄰居

有了這個公式後，只要去思考 `maxHeightFromLeft` 和 `maxHeightFromRight` 的意義就好，我們只記錄最大值這樣是合理的嗎？這時候可以看一個極端一點的例子 `[1, 100, 0, 10, 5, 200]`：在座標 `4` 的地方高度是 `5`，右側的高度我們應該要看 `10` 還是 `100`？

看 `10` 是不對的 —— 這裡要看的是**左側**的 `100`，因為 `10` 的左邊其實是 `100`，水可以一路積到 `100` 的高度。所以兩邊都必須是「到目前為止的最高值」，不是相鄰的那一根。

## 解題方向

### 解法一：預先計算左右兩側的最高值

公式需要什麼就先算出來：兩個陣列，`lmax[i]` 是 `0..i` 的最高值，`rmax[i]` 是 `i..n-1` 的最高值。掃三趟就結束了。

```python
class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        if n == 0:
            return 0
        
        lmax = [0] * n
        rmax = [0] * n

        lmax[0] = height[0]
        rmax[n - 1] = height[n - 1]

        for i in range(1, n):
            lmax[i] = max(lmax[i-1], height[i])
        
        for i in range(n - 2, -1, -1):
            rmax[i] = max(rmax[i+1], height[i])

        ans = 0
        for i in range(1, n - 1):
            ans += min(lmax[i], rmax[i]) - height[i]
        
        return ans
```

`lmax[i]` 和 `rmax[i]` 都包含 `height[i]` 自己，所以 `min(...) - height[i]` 永遠不會是負數，不用額外判斷。迴圈從 `1` 跑到 `n-2` 是因為兩端點怎麼樣都裝不了水。

這個解法最直觀，缺點是額外用了兩個長度 `n` 的陣列。

### 解法二：雙指針（空間降到 `O(1)`）

下一個難點是在於，為什麼一樣可以繼續用雙指針的方式來做遍歷？其實這個和題目的特性有關：如果左側的邊界比較矮，代表左側邊界才是決定這一格可以裝多少水的邊界，這時候就要從左邊往中間搜尋。

像是 `[5, 4, 3, 2, 1, 100]` 這時候右邊基本上是不用動的；我們要擔心的反而是 `[5, 4, 3, 2, 1, 100, 2, 3, 4, 5, 6]` 這種中間有一個很高的山峰、把兩側山谷分開的情況。從左側不斷往中間前進，走到山峰 `100` 之後才換右側往中間搜尋。

先把骨架寫出來 —— **注意這一份還沒有計算水量，`area` 從頭到尾都是 0**，只是先確立指針怎麼走：

```python
class Solution:
    def trap(self, height: List[int]) -> int:        
        if len(height) <= 2:
            return 0

        left = 0
        right = len(height) - 1
        area = 0

        while left < right:
            leftHeight = height[left]
            rightHeight = height[right]

            if leftHeight <= rightHeight:
                left += 1
            elif leftHeight > rightHeight:
                right -= 1
        return area
```

剩下一個我們需要的資訊，那就是當我從某一個方向往中間出發的時候，另一側的最大高度為何？所以我們需要有另外兩個變數來幫助我們更新位置 `i` 左右兩側的最大值。一開始的最大高度就是最兩側，是因為最左和最右側的點不管怎麼樣都一定無法儲存水份，就會把兩側端點設定為暫時的兩側最大值。

接著只剩最後一個情況要處理：也有可能這座山就是 `[1, 2, 3, 3, 2, 1]` 根本沒有任何山谷，所以不管我們怎麼往中間走，都不會有任何山谷可以存水。遇到這種情況，那就是要看當下的位置是不是比目前記錄到的最大值還高 —— 如果是的話就更新該側的最大值，該格絕對沒有辦法儲存水。

```python
class Solution:
    def trap(self, height: List[int]) -> int:        
        if len(height) <= 2:
            return 0

        left = 0
        right = len(height) - 1

        maxHeightFromLeft = height[0]
        maxHeightFromRight = height[len(height) - 1]

        area = 0

        while left < right:

            leftHeight = height[left]
            rightHeight = height[right]

            if leftHeight <= rightHeight:

                if leftHeight >= maxHeightFromLeft:
                    maxHeightFromLeft = leftHeight
                else:
                    area += maxHeightFromLeft - leftHeight
                left += 1

            elif leftHeight > rightHeight:

                if rightHeight >= maxHeightFromRight:
                    maxHeightFromRight = rightHeight
                else:
                    area += maxHeightFromRight - rightHeight
                right -= 1

        return area
```

### 為什麼只看一側的最大值就夠

上面說「左側比較矮就從左邊走」是直覺，但真正該問的是：算 `left` 這一格時，**根本不知道右側真正的最大值**，怎麼敢只用 `maxHeightFromLeft`？

理由和 [11](/interview/coding/11-container-with-most-water) 是同一套論證。當 `height[left] <= height[right]` 時：

- `maxHeightFromLeft` 是 `0..left` 的真實最高值，這個沒有疑問
- 而右側**保證存在一根不低於 `maxHeightFromLeft` 的柱子**

第二點是關鍵。`maxHeightFromLeft` 是由某一個位置設定的，而那個位置當初能被 `left` 走過，就是因為它當時 `<=` 當時的 `height[right']`；`right` 只會往左收，所以 `maxHeightFromRight ≥ height[right'] ≥ maxHeightFromLeft`。

於是 `min(maxHeightFromLeft, 真正的右側最大值)` 一定就是 `maxHeightFromLeft` —— 短板在左邊，右邊有多高都不影響這一格的答案。所以不需要知道右側的真實最大值，這就是能把空間從 $O(n)$ 降到 $O(1)$ 的原因。

### 解法三：單調棧

前兩種解法都是「對每一格算它上面的水」。單調棧換一個角度：**一次結算一整個凹陷**。

維護一個棧，裡面存索引，對應的高度由底到頂**遞減**。遞減的棧代表「還在等右牆的柱子」。當遇到一根比棧頂高的柱子，就表示右牆到了，可以結算：

- `bottom = stack.pop()` —— 凹陷的**底**
- `left = stack[-1]` —— pop 完之後的新棧頂就是**左牆**
- 寬度是兩牆之間的距離 `i - left - 1`，深度是 `min(左牆, 右牆) - 底`

```python
class Solution:
    def trap(self, height: List[int]) -> int:
        stack = []          # 存索引，對應的高度由底到頂遞減
        area = 0

        for i, h in enumerate(height):
            while stack and height[stack[-1]] < h:
                bottom = stack.pop()            # 凹陷的底部
                if not stack:                   # 左邊沒有牆，水會流掉
                    break
                left = stack[-1]                # 左牆
                width = i - left - 1
                depth = min(height[left], h) - height[bottom]
                area += width * depth
            stack.append(i)

        return area
```

兩個容易寫錯的地方：

1. **pop 完要檢查棧是不是空了。** 空的表示左邊沒有更高的柱子，這個凹陷沒有左牆，水會流掉，直接 `break`。
2. **寬度是 `i - left - 1` 而不是 `i - left`。** 兩牆之間的格子數要把兩道牆本身扣掉。

相同高度時用 `<` 或 `<=` 都可以 —— 高度相同時 `depth` 算出來是 0，加了也沒差。

這個解法的價值在於**它會推廣**：同一套「遞減棧 + 遇到更高的就結算」的手法可以直接搬去解 [84. Largest Rectangle in Histogram](/interview/coding/84-largest-rectangle-in-histogram)，見 [單調棧模板](/interview/coding/monotonic-stack-template)。雙指針那版比它省空間，但只對這一題有效。

## 補充

**和 [11. Container With Most Water](/interview/coding/11-container-with-most-water) 的差別**是最容易搞混的地方：11 是挑**兩根**柱子當桶壁求一個最大配對，所以矮的那邊可以直接丟掉；42 是**每一格**都要算貢獻再加總，所以必須知道兩側的最高值。圖長得幾乎一樣，問法完全不同。

## 複雜度

**預先計算左右兩側的最高值**
- 時間 $O(n)$ — 三趟線性掃描
- 空間 $O(n)$ — 兩個長度 `n` 的輔助陣列

**雙指針**
- 時間 $O(n)$ — 兩個指針總共走完陣列一次
- 空間 $O(1)$ — 只有兩個指針和兩個最大值變數

**單調棧**
- 時間 $O(n)$ — 每個索引最多進棧一次、出棧一次
- 空間 $O(n)$ — 最壞情況（高度嚴格遞減）整個陣列都在棧裡

其中 $n$ 是柱子的數量。三者時間都一樣，差別在空間和用途：

- **雙指針**空間最省，是面試被追問「能不能不用額外陣列」時要給的答案
- **預先計算**最直觀，適合先講出來確認方向對不對
- **單調棧**空間沒有優勢，但它是唯一會推廣到其他題的解法