LC 42接雨水Trapping Rain Water　困难

给定一排柱子的高度，计算下雨后每根柱子上方能接住的雨水总量。

思路 双指针 + 两侧最大值：每个位置水量由左右最大高度的较小者决定，哪侧最大值小先结算哪侧。时间 O(n)、空间 O(1)。

class Solution:
    def trap(self, height: List[int]) -> int:
        ans = pre = suf = 0
        l, r = 0, len(height) - 1
        while l < r:
            pre = max(pre, height[l])
            suf = max(suf, height[r])
            if pre < suf:
                ans += pre - height[l]
                l += 1
            else:
                ans += suf - height[r]
                r -= 1
        return ans