leetcode：42. 接雨水【双指针很优雅】

分析

双指针从最左最右开始
一个个比较height，如果当前这个小就往内移动
用leftMax和rightMax记录左右两边遍历过的最大的值
要知道的是，当前移动的那一端，一定是被比下去的，也就是说当前没移动的那一个点一定是目前最大的
因此比如左边移动了，它这个一定会被leftMax和height[j]包围，并且leftMax一定是小的，所以贡献就是leftMax - height[i]

ac code

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height:
            return 0
        i, j = 0, len(height) - 1
        leftMax, rightMax = height[0], height[-1]
        ans = 0

        while i <= j:
            leftMax = max(leftMax, height[i]) # 左边max
            rightMax = max(rightMax, height[j]) # 右边max

            # 中间ij判断
            if height[i] < height[j]:
                # height[i]被leftmax和height[j]夹着,leftmax更小（不然不会挪走）
                ans += leftMax - height[i]
                i += 1
            else:
                # height[j]被rightmax和height[i]夹着,rightmax更小（不然不会挪走）
                ans += rightMax - height[j]
                j -= 1
        
        return ans
        

总结

接雨水双指针最为优雅