LeetCode 42: Trapping Rain Water题解（python）

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