6.23 - hard - 9

42. Trapping Rain Water
这题的思路比较简单明确，就是找出当前点的左边最高和右边最高，然后取其中的小值来减去当前的高度就是当前点的蓄水量了。

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        # 这道题的思路就是找到一个值左边的最高点和右边的最高点，然后取短的并且减去当前的值
        
        if not height or len(height) <= 2:
            return 0
        left = [0]
        for i in range(1, len(height)):
            left.append(max(height[i-1], left[-1]))
        
        right = [0]
        for i in range(len(height)-2, -1, -1):
            right = [max(right[0], height[i+1])] + right
        
        
        res = 0
        for i in range(1, len(height)-1):
            res += max(min(left[i], right[i]) - height[i], 0)
        
        return res