「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
您必须登录才能发表评论。