LeetCode 刷题记录: 42. Trapping Rain Water [Python]

原题

https://leetcode.com/problems/trapping-rain-water/

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

思路

使用双指针，分别从两头往最高处逼近。每次经过刷新左边和右边的最高值，该处结果等于最高值与当前值的差。

代码

class Solution:
    def trap(self, height: List[int]) -> int:
        res=0
        left=0
        right=len(height)-1
        max_left=max_right=0
        while left<=right:
            if height[left]<height[right]:
                max_left=max(max_left,height[left])
                res+=max_left-height[left]
                left+=1
            else:
                max_right=max(max_right,height[right])
                res+=max_right-height[right]
                right-=1
        return res

# LeetCode, Triky

支付宝

微信

Paypal Buy me a coffee

LeetCode 刷题记录: 42. Trapping Rain Water [Python]

原题

思路

代码

喜欢这篇文章？打赏一下作者吧

评论

分类

标签

最新文章

归档

最新文章

归档

Your browser is out-of-date!