接雨水

题目要求

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

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

思路分析

思考才是最重要的

这个题目非常好的诠释了一句话----“技术，只是实现目标的方式和手段”。

很多人面对问题时，总是有一种较劲脑汁写算法的冲动，还有人，以为每一种问题都有一个成熟的解决方案，似乎接触过这个方案并记忆下来，今后再遇到时就可以迎刃而解了。殊不知，编程是一个创造性的思考过程，很多人不愿意思考，更喜欢走马观花般的背答案。短时间内的确可以提升算法能力，但长期来看，你的逻辑能力才是解决问题的根本，思考才是第一位的。

两个基本判断

我们先不去想怎么写算法，而是先分析，抽丝剥茧的对这个问题进行分析。

首先，最左侧的柱子和最右侧的柱子上面不可能存储雨水，这个判断很简单，不做讨论。

其次，每个柱子上能存储多少水，取决于它左右两侧最高柱子的高度，以索引为5的柱子为例，这个柱子的高度是0，它左侧最高的柱子是索引为3的柱子，高度为2， 它右侧最高的柱子是索引为7的柱子，高度为3，这两个柱子的高度决定了，索引为5的柱子上面可以存储水2个单位。

算法思路

经过上面的两点分析，解题的思路就非常清晰了。

遍历数组，计算每个柱子左右两侧的最高柱子的高度，这两个高度中选最小的，如果这个最小高度大于当前柱子的高度，那么差值就是当前这个柱子能够存储的水的量。

由于遍历的过程是从左向右，因此，左侧最高柱子的高度可以用一个变量保存起来，而右侧最高柱子的高度则需要每次都去计算,但是经过一次寻找后，这个最高柱子的位置就确定了，假设位置为K，对于这个柱子左侧的所有柱子来说，他们右侧的最高柱子都是固定的，因此，也可以存储起来，直到遍历过程中当前柱子的索引大于等于K，则需要重新寻找。

实例代码

def trap(lst):
    left_height = 0
    right_index = 0
    rain = 0
    for index, item in enumerate(lst):
        # 第一个和最后一个不用考虑，因为柱子上方无法存储水
        if index == len(lst) - 1 or index == 0:
            left_height = item
            continue

        # 如果左侧最高为0或者和当前高度相同，当前这个柱子的上方无法存储水
        if left_height == 0 or left_height == item:
            left_height = item
            continue

        # 获取右侧最高的柱子高度， 取左右两侧较矮的，如果当前柱子高度小于它，则可以存储水
        if index >= right_index:
            right_index, right_heigth = find_right_heigth(index, lst)

        min_heigth = min([left_height, right_heigth])
        if min_heigth > item:
            rain += min_heigth - item

        # 更新左侧最高柱子的高度
        if item > left_height:
            left_height = item

    return rain


def find_right_heigth(index, lst):
    """
    返回index右侧最高柱子的位置和高度
    :param index:
    :param lst:
    :return:
    """
    right_heigth = 0
    right_index = index
    for i in range(index, len(lst)):
        if lst[i] > right_heigth:
            right_index = i
            right_heigth = lst[i]

    return right_index, right_heigth


if __name__ == '__main__':
    lst = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]

    print(trap(lst))