42 Trapping Rain Water

两种思路：第一种 brute force : 主要是记录两侧积水的最大值的最小值减去当前的高度得到数值。=> 超时

第二种思路是将上述过程中的一遍一遍扫描的结果记录下来，这样可以减少之后的扫描次数。

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        left, right = 0, len(height) - 1
        ans = 0
        for i in range(1, len(height) - 1):
            max_left = 0
            max_right = 0
            for j in range(i, -1, -1):
                max_left = max(max_left, height[j])
            for j in range(i, len(height)):
                max_right = max(max_right, height[j])
            min_height = min(max_left, max_right)
            if min_height - height[i]:
                ans += min_height - height[i]
        return ans

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        if height == []:
            return 0
        pre = []
        after = []
        length = len(height)
        maxval = height[0]
        maxval_after = height[-1]
        for i in range(length):
            if height[i] <= maxval:
                pre.append(maxval)
            else:
                pre.append(height[i])
                maxval = height[i]
            if height[length-1-i] <= maxval_after:
                after.insert(0,maxval_after)
            else:
                after.insert(0,height[length-i-1])
                maxval_after = height[length-i-1]
        ans = 0
        for i in range(length):
            ans += min(pre[i],after[i]) - height[i]
        return ans