LeetCode 42. Trapping Rain Water 时间复杂度（O(n))

class Solution:
    def trap(self, height: List[int]) -> int:
        def one_search(height):
            pre_v = 0
            res = []
            for index, h in enumerate(height):
                if index == 0:
                    pre_v = h
                    res.append(0)
                else:
                    if pre_v >= h:
                        res.append(pre_v - h)
                    else:
                        pre_v = h
                        res.append(0)
            return res
        res = one_search(height)
        res2 = one_search(height[::-1])
        res2 = res2[::-1]
        res = [min(r1, r2) for r1, r2 in zip(res, res2)]
        return sum(res)

两次遍历，动态规划