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
由此图示可见,有六个单位面积的蓝色,对应着六个单位面积的积水。
链接: 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
下一篇: 2016年 SEO还有哪些变现的途径?