【LeetCode最详尽解答】42-接雨水 Trapping-Rain-Water

本文主要是介绍【LeetCode最详尽解答】42-接雨水 Trapping-Rain-Water，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

欢迎收藏Star我的Machine Learning Blog:https://github.com/purepisces/Wenqing-Machine_Learning_Blog。如果收藏star, 有问题可以随时与我交流, 谢谢大家！

链接:

42-接雨水

直觉

通过可视化图形来解决这个问题会更容易理解和解决。

给定输入: 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 个单位的雨水被困住。

最初，我尝试同时移动左指针和右指针，但在到达右半部分 [3,2,1,2,1] 时遇到了问题。这时，左指针指向值 3，而右指针指向数组的末尾。右边界值小于左边界值，无法形成雨水陷阱。

这是错误的解决方案：

class Solution(object):def trap(self, height):""":type height: List[int]:rtype: int"""l = 0 r = 1area = 0while l < r and r < len(height)-1 :while height[r] < height[l] and r < len(height)-1 :r+=1for i in range(l+1,r):area+=height[l] -height[i]l = rr = l +1return area

然后，我观看了 NeetCode 的视频，他将左右指针分别初始化为数组的起始和结束位置。此外，还使用了两个变量 leftmax 和 rightmax。每次移动较小的值并将当前面积累加到最终结果中。如果 rightmax 较小，它会向左移动，因为无法从左指针陷阱雨水，并加上当前面积值 rightmax - height[r]。相反，如果 leftmax 较小，则加上面积值 leftmax - height[l] 并向右移动检查下一个值。

方法

初始化两个指针 left 和 right，分别位于数组的起始和结束位置。
初始化 leftmax 和 rightmax 为起始和结束位置的值。
移动较小的值并更新最大值，将面积值累加到最终结果中。

复杂度

时间复杂度:
$O (n)$
- 我们遍历数组一次，因此时间复杂度是线性的。
空间复杂度:
$O (1)$
- 无论输入大小如何，我们只使用常量数量的额外空间。

代码

class Solution(object):def trap(self, height):""":type height: List[int]:rtype: int"""l = 0r = len(height)-1leftmax = height[l]rightmax = height[r]res = 0while l < r:if leftmax < rightmax:l+=1leftmax = max(leftmax, height[l])res += leftmax - height[l]else:r-=1rightmax = max(rightmax, height[r])res += rightmax - height[r]return res