博客

给定

n

个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

感谢 Marcos

贡献此图。

示例:

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

思路：

每个位置上积水的高度，应该等于min（左边最高的柱子高度，右边最高的柱子高度） –  这个位置上的柱子高度。

所以先从左往右遍历把left_max数组生成，left_max[i]代表 height[i] 及其左侧最高的柱子高度。

同理生成right_max。

然后再遍历一次对于每个位置计算min(left_max[i], right_max[i]) – height[i]就好了

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        left_max = [0 for _ in height]
        right_max = [0 for _ in height]
        water = [0 for _ in height]
        
        for i in range(len(height)):
            if i - 1 >= 0:
                left_max[i] = max(left_max[i - 1], height[i])
            else:
                left_max[i] = height[i]
            
        for i in range(len(height) - 1, -1, -1):
            if i  < len(height) - 1:
                right_max[i] = max(right_max[i + 1], height[i])
            else:
                right_max[i] = height[i]
                
        for i in range(len(height)):
            tmp = min(left_max[i], right_max[i]) - height[i]
            if tmp > 0:
                water[i] = tmp
        # print height     
        # print water
        # print left_max
        # print right_max
        return sum(water)