每日leetcode——42. 接雨水数据结构与算法

题目给定 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

【每日leetcode——42. 接雨水】时间复杂度：O(n^2)，每遍历一个元素，就要遍历一次数组
空间复杂度：O(1)