Leetcode題解 Python：Trapping Rain Water

給一個代表(牆)高度的非負整數數列，而下雨之後，水會積在低窪處，回傳水的體積。

水會積多少，取決於左右方的最高高度取較低者減當前高度，若小於零代表沒有積水。

這樣子很好寫出正確寫法，但是超時的問題得考慮進去。

如果每次都重找最大值，時間複雜度會是 O(n**2)，得想辦法拉到 O(n) 解決。

最大值一定要重找嗎？如果從左方開始，左方的最大值會一路遞增，而右方會一路遞減。過了數列的最大值，消漲就會互換。

也就是說，若能使用 TwoPointer 去從左右方往中間靠近，邊找邊算所求，就能把時間複雜度用在 O(n)。

當然可以做到，官方也有範例可供參考。

Python(基本)

class Solution:
    def trap(self, height: List[int]) -> int:
        result = 0
        n = len(height)
        for i in range(1,n-1):
            lmax = max(height[:i])
            rmax = max(height[i:])
            result += max(min(lmax, rmax) - height[i], 0)
        return result

Python(進階)

class Solution:
    def trap(self, height: List[int]) -> int:        
        result = 0
        li, lmax = 0, 0
        ri, rmax = len(height)-1, 0
        while li <= ri:
            if lmax > rmax:                
                if height[ri] > rmax: rmax = height[ri]                   
                else: result += rmax - height[ri] 
                ri -= 1
            else:
                if height[li] > lmax: lmax = height[li]                                   
                else: result += lmax - height[li]
                li += 1                
        return result