阅读量

原创教程,严禁转载。引用本文,请署名 Python中文网, http://www.zglg.work


单调栈使用总结

最近有几位球友问我,不知道怎么使用单调栈解决实际问题,今天我通过一道leetcode题目,来详细解读如何使用单调栈。

单调栈

单调栈是指栈内元素组织有序的栈,分为单调递增栈和单调递减栈。

如下为单调递增栈:

1->3->5->7

如下为单调递减栈:

7->5->3->1

下面分析单调栈的应用,节选自LeetCode

最大圆柱面积

给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。

求在该柱状图中,能够勾勒出来的矩形的最大面积。

以上是柱状图的示例,其中每个柱子的宽度为 1,给定的高度为 [2,1,5,6,2,3]。

图中阴影部分为所能勾勒出的最大矩形面积,其面积为 10 个单位。

示例:

输入: [2,1,5,6,2,3] 输出: 10

来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/largest-rectangle-in-histogram

首先判断能不能使用单调栈。若能,使用单调栈解决问题,需要找出栈内存储何值,何时入栈值,何时出栈值这三个问题。

因为勾勒出的圆柱中间不能出现任何空心,所以一旦出现如下驼峰结构,便表明到以此局部极大值时,圆柱最大面积被找到,枚举此局部区域所有可能的面积值,标记出最大值。

举个例子说明上面的分析,如下结构:

[2, 3, 5, 3]

此结构在index=2时,达到局部极大值5,形成一个上面提到的驼峰结构,且[2, 3, 5]是单调递增的一侧,index=2时达到顶峰,到index=2时,一定存在一个局部最大圆柱面积,可能的圆柱面积有:

height * width, 即:
5 * 1
3 * 2
2 * 3

即局部最大面积为 : 6

上面的分析恰好借助单调栈完美实现,为什么? 第一,我们需要驼峰左侧即单调递增侧,所以单调递增栈能帮助我们做到。第二,单调递增栈存储元素的index,当前cur元素大于nums[stack[-1]]时入栈即可。

当前cur元素小于nums[stack[-1]]时,表明元素nums[stack[-1]]就是局部极大值,驼峰处index就是 stack[-1],此时栈内形成的就是驼峰左侧单调递增区域。

然后,我们逐次出栈stack,就是模拟上面的计算所有可能的圆柱面积,标记处局部极大面积即可。

所以单调递增栈能够完美实现我们的分析过程。

局部极大面积值

上面提到局部极大值,为什是局部极大面积值?因为我们从输入列表heights中,可能找到多个驼峰。如下输入:

[3, 4, 1, 5, 6, 3, 2, 5]

可能的驼峰结构有:

[3, 4, 1]

[1, 5, 6, 3]

[3, 2, 5]

所以我们需要综合考虑,上面每个驼峰结构,并找出最大面积值。

伪代码

    def largestRectangleArea(heights: List[int]) -> int:
        # 创建栈
        stack <- []
        # 遍历heights
        for i in range(length):
            # 满足while条件表明找到局部驼峰
            while stack is not empty and heights[i] smaller than stack top:
                # 逐次出栈
                p <- stack.pop(-1)
                # 找到一个可行解
                height, width <- heights[p], i-1-stack[-1] 
                s <- max(s, width*height)
            # 不满足while条件,即要么stack为空,要么大于stack top
            stack.append(i)

        return s

实现细节用到哨兵

我们不能忽视对边界情况的处理,对于如下单调递增的输入测试例子:

[3, 5, 7]

根据上面伪代码,元素会一直append到stack中,直到退出,返回圆柱面积s为0,这显然是错误的。

如果在输入列表heights尾部添加一个哨兵值0,问题会得到解决,因为输入列表内元素值都是正整数。添加0后,在index=2,元素7处必然达到驼峰,然后逐次出栈找到所有可能圆柱面积的最大值。

但是仅仅尾部添加一个哨兵值0就够了吗?注意观察,若我们的输入序列为如下,并且尾部添加一个哨兵值0:

[2, 1, 3, 5, 7, 0]

第一次进入while条件时,stack内只有一个值(即index=0),执行 p <- stack.pop(-1)出栈后,stack变为空,所以stack[-1]会抛出异常。为解决此问题,同样在index=0处插入一个哨兵值0,作用为了防止抛出empty stack reference error

综上所述,要在输入列表heights两头各插入一个哨兵值0,便能完美解决上面两个问题:

  • 元素会一直append到stack中,直到退出,返回圆柱面积s为0,这显然是错误的。
  • empty stack reference error

完整代码

如果理解上面的分析和两个哨兵后,便不难看懂下面代码:

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        length = len(heights)
        if length == 0:
            return 0

        stack, s = [], 0

        # 两头各插入1个哨兵
        heights.insert(0,0)
        heights.append(0) 
        length += 2

        for i in range(length):
           # 满足while意味着找到一个驼峰     
            while len(stack)!=0 and heights[i]<heights[stack[-1]]:   
                p = stack.pop(-1)
                width = i - stack[-1] - 1
                height = heights[p]
                s = max(s, width * height)

            # 正在形成驼峰左侧
            stack.append(i)

        return s

复杂度分析

相对于暴力枚举的$O(n^2)$时间复杂度,单调栈牺牲$O(n)$的空间复杂度,换来一种$O(n)$的时间复杂度实现,这是值得的!


以上就是单调栈的分析,和实际应用,希望对你有些帮助。我们下一篇见!