1. FlyPython首页
  2. 数据结构与算法
  3. leetcode题解

「LeetCode每日一题」—— 42. 接雨水

42. 接雨水

链接:https://leetcode-cn.com/problems/trapping-rain-water/
难度:困难

题目

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。

上面是由数组 [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

思路

这是每日一题第一道困难题。

要计算几个单位的雨水,其实就是要确定左右边界。雨水的容量由左右边界的最大值中的较小值决定,所以就转化为求左右边界最大值。

我们使用两个指针,从左右往中间移动,移动中维护最大值,高度差叠加就是答案。

方案代码

class Solution:
    def trap(self, height: List[int]) -> int:
        n = len(height)
        if n == 0:
            return 0
    
        left, max_left = 0, height[0]
        right, max_right = n-1, height[n-1]

        ans = 0
        while(left<right):
            if max_left <= max_right:
                ans += max_left - height[left]
                left += 1
                max_left = max(height[left],max_left)
            
            if max_left > max_right:
                ans += max_right - height[right]
                right -= 1
                max_right = max(height[right],max_right)
        
        return ans      

原创文章,作者:flypython,如若转载,请注明出处:http://flypython.com/algorithm/leetcode/307.html