42. Trapping Rain Water

──────────────────────────────────────────────────────────────────────

42. Trapping Rain Water

要寫這一題之前，要先了解 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，因為他們那一個格子的容量，都被兩邊高度的最小值給決定了。於是每一格的水量就是：

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 的最高值。掃三趟就結束了。

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，只是先確立指針怎麼走：

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] 根本沒有任何山谷，所以不管我們怎麼往中間走，都不會有任何山谷可以存水。遇到這種情況，那就是要看當下的位置是不是比目前記錄到的最大值還高 —— 如果是的話就更新該側的最大值，該格絕對沒有辦法儲存水。

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 是同一套論證。當 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(左牆, 右牆) - 底

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，見 單調棧模板。雙指針那版比它省空間，但只對這一題有效。

補充

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

複雜度

預先計算左右兩側的最高值

• 時間 $O(n)$ — 三趟線性掃描
• 空間 $O(n)$ — 兩個長度 n 的輔助陣列

雙指針

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

單調棧

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

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

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