LeetCode-python 42.接雨水

阿里云2000元红包!本站用户参与享受九折优惠!

题目链接
难度:困难       类型: 栈


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

示例

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

解题思路


图片来源于 https://leetcode-cn.com/problems/two-sum/solution/jie-yu-shui-by-leetcode/

  • 找到数组中从下标 i 到最左端最高的条形块高度 \text{left_max}
  • 找到数组中从下标 i 到最右端最高的条形块高度 \text{right_max}
  • 扫描数组 \text{height}并更新答案:
    累加 \min(\text{max_left}[i],\text{max_right}[i]) - \text{height}[i]到 总面积上

代码实现

 class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        max_left = [0]         
        for h in height:             
            max_left.append(max(max_left[-1], h))
        max_right = 0    
        res = 0
        n = len(height)
        for i in range(n):
            max_right = max(max_right, height[n-i-1])
            
            res += min(max_right, max_left[n-i]) - height[n-i-1]
        return res

你或许想:《去原作者写文章的地方

「点点赞赏,手留余香」

    还没有人赞赏,快来当第一个赞赏的人吧!
Python
0 条回复 A 作者 M 管理员
    所有的伟大,都源于一个勇敢的开始!
欢迎您,新朋友,感谢参与互动!欢迎您 {{author}},您在本站有{{commentsCount}}条评论