欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

LeetCode 42: Trapping Rain Water题解(python)

程序员文章站 2022-10-04 09:59:31
Leetcode 42: Trapping Rain Water分类:Stack (Monotonic Stack)难度:Hard (H-/M+)描述:给了一个整数数组,这个数组可以模拟成一个积水的槽。问这个水槽最大能积多少个单位面积的水Input: [0,1,0,2,1,0,1,3,2,1,2,1]Output: 6由此图示可见,有六个单位面积的蓝色,对应着六个单位面积的积水。链接: Trapping Rain Walter.思路:此题主要思路是维护一个递减栈。当遇到一个不断递减的b...

Leetcode 42: Trapping Rain Water

分类:Stack (Monotonic Stack)
难度:Hard (H-/M+)
描述:给了一个整数数组,这个数组可以模拟成一个积水的槽。问这个水槽最大能积多少个单位面积的水
Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

LeetCode 42: Trapping Rain Water题解(python)
由此图示可见,有六个单位面积的蓝色,对应着六个单位面积的积水。
链接: Trapping Rain Walter.

思路:

此题主要思路是维护一个递减栈。当遇到一个不断递减的bar时,元素入栈。当遇到高的bar时,栈顶元素先行pop出来作为一个洼地,即base,然后储水面积的高度取决于栈顶元素与扫描到的元素中小的那个,宽度取决于扫描元素的位置以及弹出一次后stack的栈顶元素的前一个位置。
如:[6,4,3,2,1,5]这个水槽,当扫描到5时,高度为min(2, 5), 宽度为5 - 3 - 1,然后把1pop掉,栈顶元素为2,对应高度min(3, 5),宽度 5-2-1。以此类推,把3,4都可以弹出然后5入栈,计算结束。把上述过程中得到的矩形相加即是结果

class Solution:
    def trap(self, height: List[int]) -> int:
        if not height or len(height) == 0: 判断边界条件
            return 0
        stack = []
        res = 0
        for i in range(len(height)):
            while len(stack) != 0 and height[stack[-1]] < height[i]: 维护递减栈。栈空时不弹出
                area = 0
                base = height[stack.pop()] 栈顶元素的位置对应着洼地的高度
                if len(stack) == 0: break 栈空时不做后续操作
                h = min(height[i], height[stack[-1]]) - base
                w = i- stack[-1] - 1
                area = h*w
                res += area
            stack.append(i) 入栈
        return res        
个人总结:

1)此题考查的是单调栈的内容。对于维护单调栈的题型注意判断栈空情况。
2)此题与84题类似。84题维护的是一个递增栈。

参考:

链接: 参考.

本文地址:https://blog.csdn.net/Bourns_A/article/details/107357716