栈 使用案例总结
共 5910字,需浏览 12分钟
·
2021-03-21 18:22
最近有几位球友问我,不知道怎么使用单调栈解决实际问题,今天我通过一道leetcode题目,来详细解读如何使用单调栈。
1 单调栈
单调栈是指栈内元素组织有序的栈,分为单调递增栈和单调递减栈。
如下为单调递增栈:
1->3->5->7
如下为单调递减栈:
7->5->3->1
下面分析单调栈的应用,节选自LeetCode
2 最大圆柱面积
给定 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
3 为什么能用单调栈?
首先判断能不能使用单调栈。若能,使用单调栈解决问题,需要找出栈内存储何值,何时入栈值,何时出栈值这三个问题。
因为勾勒出的圆柱中间不能出现任何空心,所以一旦出现如下驼峰结构,便表明到以此局部极大值时,圆柱最大面积被找到,枚举此局部区域所有可能的面积值,标记出最大值。
举个例子说明上面的分析,如下结构:
[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
,就是模拟上面的计算所有可能的圆柱面积,标记处局部极大面积即可。
所以单调递增栈能够完美实现我们的分析过程。
4 局部极大面积值
上面提到局部极大值,为什是局部极大面积值?因为我们从输入列表heights
中,可能找到多个驼峰。如下输入:
[3, 4, 1, 5, 6, 3, 2, 5]
可能的驼峰结构有:
[3, 4, 1]
[1, 5, 6, 3]
[3, 2, 5]
所以我们需要综合考虑,上面每个驼峰结构,并找出最大面积值。
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
6 用到哨兵
我们不能忽视对边界情况的处理,对于如下单调递增的输入测试例子:
[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
7 完整代码
如果理解上面的分析和两个哨兵后,便不难看懂下面代码:
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
复杂度分析
相对于暴力枚举的
以上就是单调栈的分析和实际应用,希望对你有些帮助,《Python与算法社区》原创作品。我们下一篇见!