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

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

flypython • • leetcode题解

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

赞 (0)
flypythonflypython
0 0 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
« 上一篇 03/04/2020 10:41
下一篇 » 05/04/2020 10:43

相关推荐