接雨水

题目要求

给定 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))

扫描关注, 与我技术互动

QQ交流群: 211426309

加入知识星球, 每天收获更多精彩内容

分享日常研究的python技术和遇到的问题及解决方案