LeetCode——–接雨水python
119 浏览量
2020-12-21
16:30:55
上传
评论
收藏 252KB PDF 举报
LeetCode——–接雨水接雨水python
题目不重述了。
小菜一枚，思路还是比较欠缺，按照leetcode题解的精选，用python写了一下。加深理解吧。
按行接雨水按行接雨水：
思路：首先寻找数组的最大值，即最多一共有几行。然后分别求每一行的雨水量。
从第一行开始，第一种情况是遇到比第一行低的块，可以存到一方水；第二种情况是遇到和第一行一样高或者比第一行要高的块，重新开始计算雨水量。
直到最高行，雨水量计算完毕。思路比较清晰，可以看力扣官网题解精选有图。
python代码：
class Solution:
def trap(self, height: List[int]) -> int:
heightest=max(height)
ans=0
for i in range(1,heightest):
start=False
temp=0
for j in range(len(height)):
if start and height[j]=i:
ans=ans+temp
temp=0
start=True
return ans
怎么统计每一行的值？什么情况开始什么时候结束才能准确统计到？开始和结束判断这些水是不是连着的。
默认是不开始的，这个位置的前面要有一个至少和当前行一样高的高度，且这个位置的高度比当前行的高度低的时候才有水。即遇到和当前行一样高或者更
高的位置开始，统计比当前行低的位置，每次加1.（这就是按行的好处，只要有水，每次固定加1），再遇到和当前行等高或更高的位置时，要重新开始。
时间复杂度：如果最大的数是 m，个数是 n，那么就是 O(m*n)O(m∗n)。
空间复杂度：O(1)。
按列接雨水：按列接雨水：
对于所要求的列，找到左边最高的点max1和右边最高的点max2，取两个最高点中比较低的点min(max1,max2)。
当所在的列比这个min要低的时候，才可能存水，存水量是min与这列的高度差。
将每一列的存水量相加就是总的水量。
代码：
评论0
最新资源