接雨水的算法
题目https://i-blog.csdnimg.cn/direct/85f2b29c8f6144d89a023318f35fe91a.png
代码
# 接雨水算法
def trap(height):
# 1. 特殊情况：数组为空 则返回0
if not height:
return 0
n = len(height)
# 2. 初始化左右指针，左右最大值，结果
left, right = 0, n - 1
# maxleft代表左边最大值，maxright代表右边最大值
maxleft, maxright = height, height
# ans代表结果
ans = 0
# 左右指针相遇时结束
while left <= right:
# 更新左右最大值
maxleft = max(height, maxleft)
maxright = max(height, maxright)
# 判断左右最大值，小的一边进行计算
# 雨滴的高度为左右最大值中的小值减去当前高度
if maxleft < maxright:
ans += maxleft - height
left += 1
else:
ans += maxright - height
right -= 1
return ans
# 计算数据 height =
height =
print(trap(height))# 6
思路
中文表明
[*]特殊环境处理：如果输入的高度数组为空，则返回0。
[*]初始化：定义左右指针left和right，分别指向数组的两端。定义maxleft和maxright，分别表现左边和右边的最大值。定义ans用于存储结果。
[*]循环盘算：当左右指针没有相遇时，进行以下操作：
[*]更新maxleft和maxright，分别为当前指针位置的高度和之前最大值中的较大者。
[*]比较maxleft和maxright，选择较小的一边进行盘算：
[*]如果maxleft较小，则盘算左边的雨水高度，并将左指针右移。
[*]否则，盘算右边的雨水高度，并将右指针左移。
[*]返回结果：循环结束后，返回盘算得到的雨水总量ans。
图示
以下是一个示例图示，展示了算法的工作原理：
高度数组:
初始状态:
left -> 0
right -> 11
maxleft -> 0
maxright -> 1
ans -> 0
每一步的状态变化:
1. left -> 1, maxleft -> 1, ans -> 0
2. right -> 10, maxright -> 2, ans -> 0
3. left -> 2, maxleft -> 1, ans -> 1
4. left -> 3, maxleft -> 2, ans -> 1
5. right -> 9, maxright -> 2, ans -> 2
6. right -> 8, maxright -> 2, ans -> 2
7. right -> 7, maxright -> 3, ans -> 2
8. left -> 4, maxleft -> 2, ans -> 2
9. left -> 5, maxleft -> 2, ans -> 4
10. left -> 6, maxleft -> 2, ans -> 5
11. left -> 7, maxleft -> 3, ans -> 6
最终结果: 6
通过上述步骤，算法盘算出总共可以接住6个单元的雨水。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]