---
image: https://leetcode.com/static/images/LeetCode_Sharing.png
tags: leetcode
---
# Week.3.HARD [42. Trapping Rain Water]
---
- 給一串數列表示牆高, 算出可以承接的雨水, 例如[0,1,0,2,1,0,1,3,2,1,2,1], 結果就是 6 (藍色部分)
- 
---
- 類似[11.Container With Most Water]一樣是雙index,基本掃起來
- 這次res要用+=累計, 因為累積雨量
- 從低的開始, 用max去算旁邊的落差, 因為一旦遇到高的max就可以把水都存起來
- 如果其中一側比另一側高, 則換低的一邊的index移動.
---

class Solution:
    def trap(self, height: List[int]) -> int:
        left, right = 0, len(height)-1
        Lmax, Rmax = height[left], height[right]
        # 累積數據, 用+=
        res = 0
        # 掃雙index
        while left < right:
            # 從比較矮的開始
            if Lmax < Rmax:
                # 雨水只能與矮的max相減
                res += max(Lmax - height[left+1], 0)
                # 減完就可以往前移動
                left += 1 
                # 重要概念,隨著推移只需要最高max
                Lmax = max(Lmax, height[left])
            else:
                res += max(Rmax - height[right-1], 0)
                right -= 1 
                Rmax = max(Rmax, height[right])
        return res

[42. Trapping Rain Water]:https://leetcode.com/problems/trapping-rain-water/
[11. Container With Most Water]:https://hackmd.io/aT_yBbgxQG-YI5uLeDx7mw