leetcode-44-trapping-rain-water

题目描述：

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

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

示例：

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

分析

对每一列的水，只需要关注当前列，以及左边最高的墙和右边最高的墙种较矮的一个。
这里有3种情况：

• 较矮的墙 > 当前列的墙
  
  water = min(max_left, max_right) - current_height

• 较矮的墙 = 当前列的墙
  
  water = min(max_left, max_right) - current_height = 0

• 较矮的墙 < 当前列的墙
  
  water = min(max_left, max_right) - current_height = 0

根据以上思路，只需遍历每一列，然后分别求出这一列对应的两边最高的墙，然后找出较矮的一端和当前墙的高度比较。

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        sum = 0
        for i in range(1, len(height) - 1):
            # search tallest wall in left
            left_h = max(height[:i])

            # search tallest wall in right
            right_h = max(height[i+1:])

            min_tmp = min(left_h, right_h)
            if height[i] < min_tmp:
                sum += (min_tmp - height[i])

        return sum

可以注意到，上面解法中，对于每一列，我们在求它左边和右边最高的墙时都是重新遍历了一遍所有高度，在这里我们可以进行优化。用两个数组分别存储第i列左边和右边最高的墙的高度：

max_left[i] = Max(max_left[i-1], height[i-1])
max_right[i] = Max(max_right[i+1], height[i+1])

实现如下：

class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        # search tallest wall in left
        left_max = [0 for i in range(len(height))]
        for i in range(1, len(height) - 1):
            left_max[i] = max(left_max[i-1], height[i-1])

        # search tallest wall in right
        right_max = [0 for i in range(len(height))]
        for i in range(len(height) - 2, 0, -1):
            right_max[i] = max(right_max[i+1], height[i+1])

        sum = 0
        for i in range(1, len(height) - 1):
            min_tmp = min(left_max[i], right_max[i])
            if min_tmp > height[i]:
                sum += (min_tmp - height[i])
        return sum