接雨水的算法

题目

代码

1. # 接雨水算法
2. def trap(height):
3.     # 1. 特殊情况：数组为空 则返回0
4.     if not height:
5.         return 0
6.     n = len(height)
8.     # 2. 初始化左右指针，左右最大值，结果
9.     left, right = 0, n - 1
10.     # maxleft代表左边最大值，maxright代表右边最大值
11.     maxleft, maxright = height[0], height[n - 1]
12.     # ans代表结果
13.     ans = 0
14.     # 左右指针相遇时结束
15.     while left <= right:
16.         # 更新左右最大值
17.         maxleft = max(height[left], maxleft)
18.         maxright = max(height[right], maxright)
19.         # 判断左右最大值，小的一边进行计算
20.         # 雨滴的高度为左右最大值中的小值减去当前高度
21.         if maxleft < maxright:
22.             ans += maxleft - height[left]
23.             left += 1
24.         else:
25.             ans += maxright - height[right]
26.             right -= 1
27.     return ans
29. # 计算数据 height = [0,1,0,2,1,0,1,3,2,1,2,1]
30. height = [0,1,0,2,1,0,1,3,2,1,2,1]
31. print(trap(height))  # 6

复制代码

思路

中文表明

• 特殊环境处理：如果输入的高度数组为空，则返回0。
  
• 初始化：定义左右指针left和right，分别指向数组的两端。定义maxleft和maxright，分别表现左边和右边的最大值。定义ans用于存储结果。
  
• 循环盘算：当左右指针没有相遇时，进行以下操作：
  
  
  
  • 更新maxleft和maxright，分别为当前指针位置的高度和之前最大值中的较大者。
    
  • 比较maxleft和maxright，选择较小的一边进行盘算：
    
    
    
    • 如果maxleft较小，则盘算左边的雨水高度，并将左指针右移。
      
    • 否则，盘算右边的雨水高度，并将右指针左移。
      
    
    
  
  
• 返回结果：循环结束后，返回盘算得到的雨水总量ans。
  

图示

以下是一个示例图示，展示了算法的工作原理：

1. 高度数组: [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
3. 初始状态:
4. left -> 0
5. right -> 11
6. maxleft -> 0
7. maxright -> 1
8. ans -> 0
10. 每一步的状态变化:
11. 1. left -> 1, maxleft -> 1, ans -> 0
12. 2. right -> 10, maxright -> 2, ans -> 0
13. 3. left -> 2, maxleft -> 1, ans -> 1
14. 4. left -> 3, maxleft -> 2, ans -> 1
15. 5. right -> 9, maxright -> 2, ans -> 2
16. 6. right -> 8, maxright -> 2, ans -> 2
17. 7. right -> 7, maxright -> 3, ans -> 2
18. 8. left -> 4, maxleft -> 2, ans -> 2
19. 9. left -> 5, maxleft -> 2, ans -> 4
20. 10. left -> 6, maxleft -> 2, ans -> 5
21. 11. left -> 7, maxleft -> 3, ans -> 6
23. 最终结果: 6

复制代码

通过上述步骤，算法盘算出总共可以接住6个单元的雨水。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。