【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 = 1
        area = 0
        while l < r and r < len(height)-1 :
            while height[r] < height[l] and r < len(height)-1 :
                r+=1
            for i in range(l+1,r):
                area+=height[l] -height[i]
            l = r
            r = l +1
        return 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 = 0
        r = len(height)-1
        leftmax = height[l]
        rightmax = height[r]
        res = 0
        while l < r:
            if leftmax < rightmax:
                l+=1
                leftmax = max(leftmax, height[l])
                res += leftmax - height[l]
            else:
                r-=1
                rightmax = max(rightmax, height[r])
                res += rightmax - height[r]
        return res