接雨水.md

接雨水

题目描述

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

示例 1： 输入：height = [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 个单位的雨水（蓝色部分表示雨水）。 示例 2： 输入：height = [4,2,0,3,2,5] 输出：9

思路一

• 首先我们要明确，本题与盛最多水的容器不同点在于，本体的柱子是有宽度的（即1），而盛最多水的容器相当于是有一个厚度为0的板子。
• 第一种思路采取分治的方法，将每一个下标看成是宽度为1的容器，计算出每个容器能盛多少水，相加即是结果。
• 那么每一个容器能盛多少水呢？我们假设当前下标为i，那么这个容器能盛的水取决于i左边最高的柱子与i右边最高的柱子，取两者中的最小值，因为高于最高柱子的水最终会流出去。初始的最高值是当前下标对应的柱子高度，然后向中间遍历，如果遇到更高的柱子，则更新最高值。这里注意，在遍历中遇到比当前最高值矮的柱子，当前柱子的最高值不变。从两边分别遍历，得到前缀最大和后缀最大。

    pro_max = [0] * n  
    pro_max[0] = num[0]
    for i in range(1, n):
        pro_max[i] = max(pro_max[i - 1], num[i])

    suf_max = [0] * n
    suf_max[n - 1] = num[n - 1]
    for i in range(n - 2, -1, -1):
        suf_max[i] = max(suf_max[i + 1], num[i])

• 最终当前下标i能盛的水为min(pro_max[i], suf_max[i]) - num[i]，如果小于0，则说明当前下标i无法盛水，则置为0。其中pro_max[i]表示i左边最高的柱子，suf_max[i]表示i右边最高的柱子，num[i]表示当前下标i对应的柱子高度。

    res = 0
    for h, pre, suf in zip(num, pro_max, suf_max):
        res += min(pre, suf) - h

• 在遍历的过程中，我们采用了zip函数，将num、pro_max、suf_max三个列表对应位置的元素打包成一个元组，然后返回由这些元组组成的列表。这样我们就可以同时遍历三个列表了。Python 的zip 函数可以一次接收任意数量的可迭代对象（如列表、元组、字符串等），理论上没有明确的上限限制，实际受内存和解释器实现的限制。
• 时间复杂度：O(n)，空间复杂度：O(n)

思路二

• 采用双指针优化空间复杂度。
• 计算最终所接水量的计算方式还是如思路一，即计算出每个单元所能存储的水量，每个单元所存储的水量取决于当前前缀最大和后缀最大，取较小的一个再减去当前高度即可。
• 在计算前缀最大值和后缀最大值的过程中，当我们得到了一个pre_max和一个suf_max，假设前缀最大小于后缀最大，那么对于前缀最大所在的单元，即使后缀最大还有中间值没有遍历到，但是无论中间的值是比当前后缀最大小还是大都不影响结果了（前缀最大值不变，所以盛水量不变）。
• 所以我们可以采用双指针，一个指向开头，一个指向结尾，每次移动较小的一端，因为移动较小的一端，对于当前下标来说，前缀最大和后缀最大一定有一个是确定的，所以可以计算出当前下标能盛的水量，然后移动指针。

    left = ans = pre_max = suf_max = 0
    right = n - 1
    while left < right:
        pre_max = max(pre_max, num[left])
        suf_max = max(suf_max, num[right])
        if pre_max < suf_max:
            ans += pre_max - num[left]
            left += 1
        else:
            ans += suf_max - num[right]
            right -= 1

• 时间复杂度：O(n)，空间复杂度：O(1)。