42. Trapping Rain Water

Loading...LeetCode

两个问题：

1. When the column can trap water? --> height[i] < min(leftMax, rightMax)

2. How much water it can trap? --> min(leftMax, rightMax) - height[i]

暴力解法就是对每个点都往左往右找max，然后左右两个max里取较小的那一个作为限高边，时间复杂度在O(n**2)，但也可以提交。

既然是遍历array然后依靠左右max求解，那可以先遍历记录各个位置的左右max，再取遍历array记录解来求和，整个遍历三次。有点像Q238：

238. Product of Array Except Self

如果某个点i的 left max 小于等于它右边某个点j的 right max，那点i 的left max 当然也小于i自己的right max（因为 right max 在从右向左探索的过程中是递增的），由此可以优化出双指针的解法。也可以说这是个双sliding window，[maxL, l] 和 [r, maxR]两个窗口。

Brute Force

class Solution:
    def trap(self, height: List[int]) -> int:
        if len(height) <= 2: return 0
        res = 0
        for i in range(1,len(height)-1): 
            maxL, maxR = max(height[:i]), max(height[i+1:])
            gap = min(maxL, maxR) - height[i]
            res += max(0, gap) 
        return res

Three Pass

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        if n <= 2: return 0
        maxL, maxR = [0 for i in range(n)], [0 for i in range(n)] 
        maxL[0], maxR[-1] = height[0], height[-1] 

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

        return sum([min(maxL[i], maxR[i])- height[i] for i in range(n)])

Two Pointer

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        if n <= 2: return 0
        l, r = 0, n -1
        maxL, maxR = 0, 0
        res = 0
        while l <= r:
            # 因为 l 的 right max 肯定大于等于 r 的 right max
            # 所以只要 maxL 小于 r 的 right max，它就也小于 l 的 right max
            if maxL <= maxR:
                maxL = max(maxL, height[l])
                res += maxL - height[l]
                l += 1
            # vice versa
            else:
                maxR = max(maxR, height[r])
                res += maxR - height[r]
                r -= 1
                
        return res