关于数据结构与算法:每日leetcode42-接雨水

给定 n 个非负整数示意每个宽度为 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 个单位的雨水（蓝色局部示意雨水）。输出：height = [4,2,0,3,2,5]
输入：9

暴力解法尽管简略，然而这道题的暴力思路一时我还没反馈过去，花了挺久工夫才想明确咋回事。
首先，大体思路就是，遍历每个柱子，也就是遍历数组每个元素，而后每个元素为核心，向左、右两侧遍历寻找比它高的最高的柱子，这样就能计算出这个柱子上方能接多少水。

看不懂没关系，开始我也看不懂，接下来联合代码具体说一下就懂了：
1.
首先，最外层 for 循环：for i in range(1, size-1)
遍历柱子，每个柱子作为桶底，向左右两侧寻找高柱子作为桶的左右两个边
因为数组的结尾、结尾这两个柱子是边界，它们当桶底不可能造成一个桶，所以遍历的时候，是从第 2 根柱子开始到倒数第 2 根柱子完结，所以是 range(1,size-1)，而不是 range(size)

2.
接下来，每次遍历拿到作为桶底的柱子，以它为核心，向左右两侧再遍历，寻找比它高的最高的柱子，作为桶底的左右两个边

for i in range(1, size-1):
    max_left,max_right = 0,0
    # 寻找 i 右边最高的柱子
    for j in range(i+1):
        max_left = max(height[j],max_left)
    # 寻找 i 左边最高的柱子
    for k in range(i,size):
        max_right = max(height[k], max_right)

    ans += min(max_left,max_right) - height[i]

这里有几个点，比拟不容易想明确：

为什么是向左右两边寻找柱子的时候，要从它本人开始始终找到结尾、结尾，而不是只看它左右的那两个柱子；而且为什么要找最高的，而不是只有比它高就行：
因为这里容易陷入一个思考误区，就是感觉一个柱子可能接水，只有它左右相邻的两个柱子比它高，把它围起来，围成一个桶，就能够接水了。
其实并非如此，一个柱子能接水，它左右两边是要有比它高的柱子，然而这两个柱子并不是肯定要和它相邻；并且，这两个柱子不仅比它高，而且还是最高的，看图就明确了：

比方上图中，柱子 a 是以后作为桶底的柱子，a 的左右两侧柱子 -a1、a1 的确比它高，而且还和它相临，然而再向左右两侧看，-a2、a2 更高，他们围城了一个更大的桶。所以，要向左右两侧始终遍历到结尾、结尾，并且要找到最高的柱子作为桶的两边。

咱们在计算水的时候，不要想着怎么去间接计算 -a2 到 a2 围城的这个桶外面的水有多少，而是指思考某个柱子上方的水是多少就能够了，设想成柱状图，每个柱子下面的水也是一柱一柱的，不要被“水”这个字眼蛊惑了。

比方，只计算 a 柱子上方的水，这个桶较低的一边是 -a2，高度为 2，a 的宽度是 1，所以 a 柱子上方的水就是 2。
同理，也能够计算出 -a1 柱子上方的水，这时要留神，-a1 柱子自身高度为 1，占据了空间，所以要把它本身的高度减掉。
同理，也能够计算出 a1 柱子上方的水
最初，把 -a1、a、a1 三个柱子上方的水，加起来，就是 -a2、a2 围城的桶里的水了。

同理，遍历每个能够作为桶底的柱子，计算出每个桶底上方的水，最初累加起来，就是最终的答案。
遍历桶底柱子的时候，咱们不须要结尾、结尾的两个柱子，因为他俩不可能作为桶底。
而在寻找左右两测最高的桶边柱子时，要包含结尾、结尾的两个柱子，因为它们能够作为桶边。
寻找左右桶边的时候，把以后桶底这个柱子，也算在遍历范畴中了，因为如果左右两边没有比它高的柱子，那么它就既是桶底、也是桶边，能够设想成它就是一块木头桩子，显然它下面是不能接水的。所以，最初在计算接水的时候，用桶边较低高度 - 桶底本身高度，对它来说就是本人减本人等于 0，刚好合乎逻辑。
当然，你也能够在遍历时，不把桶底这个柱子算在遍历范畴内，只不过遇到左右没有比它高的柱子这种状况时，还要独自写代码解决，就比拟麻烦，所以这样写算是一个小技巧。

def trap(height) -> int:
    size = len(height)
    ans = 0
    
    # 遍历每个能够作为桶底的柱子，结尾、结尾两个柱子不能作为桶底，不在遍历范畴内
    for i in range(1,size-1):
        max_left,max_right = 0,0
        # 寻找 i 柱子左侧比本人高的最高柱子，没有的话 i 本人就是最高柱子
        # 结尾的柱子能够作为桶边，在遍历范畴内
        for j in range(i+1):
            max_left = max(height[j],max_left)
        # 寻找 i 柱子右侧比本人高的最高柱子，没有的话 i 本人就是最高柱子
        # 结尾的柱子能够作为桶边，在遍历范畴内
        for k in range(i,size):
            max_right = max(height[k], max_right)
        # 较低的桶边柱子高度 - 桶底柱子高度，就是桶底柱子上方的储水量
        # 每个桶底柱子上方储水量累加，就是最终答案
        ans += min(max_left,max_right) - height[i]
    return ans

工夫复杂度：O(n^2)，每遍历一个元素，就要遍历一次数组
空间复杂度：O(1)

题目

思路

暴力解法