文章目录

前言1.接雨水2.我的思路和代码3.大佬的思路和代码 总结

前言

看了大佬的思路然后自己把代码敲出来的，这应该勉强可以算自己写的吧。毕竟这是我写的第一个困难题，有点小兴奋。

1.接雨水

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

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

示例:

输入: [0,1,0,2,1,0,1,3,2,1,2,1] 输出: 6

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/trapping-rain-water 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2.我的思路和代码

我一开始的思路是想到了单调栈，找到大于等于它的理它最近的值，然后根据每日温度那题的写法可以很快写出来，但是发现可能会有重复的计算，如两个小的包在两个大的之间，就会算两遍。于是我想改变一下思路，看题解发现一个大佬的思路十分有趣，他是先算出每层的格数，然后减去总数，如图。(图片来自leetcode蜀笑笑大佬，仅帮助理解计算每层的格数是什么意思。) 下面是我根据大佬的思路自己写的代码:

class Solution: def trap(self, height: List[int]) -> int: if not height:return 0 n = max(height) #求出最高层数 length = len(height) sum1 = 0 for i in range(1,n+1): #从第1层遍历到第n层 mark2 = 0 #mark用来标记是否大于等于i mark1 = 0 for j in range(length): #从前遍历大于等于i的最前面那一个 if height[j] >= i: count1 = j mark1 = 1 break for k in range(length-1,-1,-1): #从后遍历大于等于i的最后面那一个 if height[k] >= i: count2 = k mark2 = 1 break if mark1 == mark2 == 1 and count2 >= count1: sum1 += (count2-count1+1) elif mark1 == 1 or mark2 == 1 :#只有一大于等于i的情况 sum1 += 1 return sum1-sum(height)

3.大佬的思路和代码

思路刚才已经介绍了，就看看大佬的代码吧。

class Solution: def trap(self, height: List[int]) -> int: n=len(height) left,right=0,n-1 SUM,tmp,high=0,0,1 while(left<=right): while(left<=right and height[left]<high): SUM+=height[left] left+=1 while(right>=left and height[right]<high): SUM+=height[right] right-=1 high+=1 tmp+=right-left+1 return tmp-SUM 作者：xiao_shi_mei 链接：https://leetcode-cn.com/problems/trapping-rain-water/solution/shuang-zhi-zhen-an-xing-qiu-geng-hao-li-jie-onsuan/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

大佬直遍历了一遍，时间复杂度为O(n),简直碾压我的时间复杂度，时间对比如下。(时间长的是我的…)

总结

第一次做困难题，感觉自己的思路还是太狭窄不知道怎么用数学的方法求出答案，明明知道这题可以用双指针做，结果不知道怎么得到题目要求的结果。所以我觉得应该多做题多看看大佬的思路开阔一下自己的思路，必要的时候可以动手画一下图，帮助理解。不过第一个困难题的成就终于得到了，还是很开心的。