（力扣记录）42.接雨水

数据结构：数组

时间复杂度：O(N)

空间复杂度：O(N)

代码实现：

class Solution:
    def trap(self, height: List[int]) -> int:
        m = len(height)
        to_left = m * [0]
        to_right = m * [0]
        can_hold = m * [0]
        max_height = 0
        
        for i in range(len(height)):
            to_left[i] = max_height
            max_height = max(max_height, height[i])

        max_height = 0

        for i in range(m-1, -1, -1):
            to_right[i] = max_height
            max_height = max(max_height, height[i])

        for i in range(len(height)):
            hold = min(to_left[i], to_right[i]) - height[i]
            if hold > 0:
                can_hold[i] = hold

        return sum(can_hold)