边工作边刷题：70天一遍leetcode: day 33-2

Trapping Rain Water

要点：很多题都是这种pattern，就是根据限定条件从两边扫描，然后比较取最终值，注意leetcode的靠前的难题到现在其实就是简单题。
错误点：

• left数组中第i个存的一定是在对应i这个点的左边值，而不是在i-1存这个值，所以在边界上是0
• 用和原数组同样长度的数组存left，别为省没意义的空间增加程序的复杂性

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        if not height: return 0
        left = height[0]
        leftsum = [0]*len(height)
        for i in range(1, len(height)-1):
            leftsum[i] = left
            
            if height[i]>left:
                left=height[i]
        
        right = height[-1]
        sum = 0
        for i in range(len(height)-2, 0, -1):
            if height[i]<min(right, leftsum[i]):
                sum+=min(right, leftsum[i])-height[i]
            
            if right<height[i]:
                right = height[i]
        return sum