Stack intro

单调栈使用总结

最近有几位球友问我，不知道怎么使用单调栈解决实际问题，今天我通过一道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