单调栈理解和实战

碎碎念：时隔多年，又回到了刷题状态，对单调栈又有了新的理解，这里记录一下作为备忘

所要解决的问题

通常单调栈用于解决：

给定数组 nums 求每个位置左右最近的大于/小于元素

典型问题：

• RFG：右最近大于
• RFS：右最近小于
• LFG：左最近大于
• LFS：左最近小于

引入例子

求当前位置的右最近大于元素(RFG)的索引，如果不存在返回数组大小

例如：

idx 0 1 2 3 4 nums = [3,1,2,4,3]

答案：

RFG = [3,2,3,5,5]

思路1：栈作为备选区

对称的版本，可以看看视频辅助理解：视频

核心思想：

当前元素去备选栈区中“找答案”

想象把栈横置作为备选答案区，盏口朝左，然后从右向左遍历

核心伪代码

注意栈中保存的是索引

# 从右往左遍历 n = len(nums) for i from n-1 -> 0: # 搜索答案，并去掉一些不可能成为答案的解，加速下轮搜索 while st非空 and nums[i] >= nums[st.top]: st.pop() RFG[i] = st.top if st非空 else n # 搜到了答案 st.push(i) # 加入备选区，开始新的一轮循环

解释

从右往左遍历求当前元素i的答案，迭代比较当前元素i和栈顶元素x（搜答案）

1.if 当前元素i >= 栈顶元素x：pop删除栈顶，并开始下一轮比较

这里在搜答案的过程中，通过pop操作删除备选区中无关的不可能成为后续迭代元素的答案的元素，从而避免重复搜索相同元素，进而加速后续元素的搜索答案过程

2.if 当前元素i < 栈顶元素x：则找到了当前元素i的RFG (右最近大于元素)为栈顶元素x

3.推论：由要点2结合算法的入栈过程，可以推断出，栈中相邻位置的元素，靠近栈底的元素是靠近栈顶元素的RFG

进阶思路2：栈作为待解区

核心思想：

入栈的元素作为待求解的元素，每次出栈时处理待求解栈顶元素，这种解法除了能够求RFG, 还能结合思路1求LFGE (左最近的大于等于)

想象将栈横置，盏口朝右

核心伪代码

# 添加哨兵元素，保证所有元素一定会pop出栈 nums.push(inf) n = len(nums) for i from 0 -> n-1: while st非空 and nums[st.top] < nums[i]: x = st.pop() RFG[x] = i # 求RFG # 同步获得的副产物 LFGE[x] = st.top if st非空 else -1 # 求LFGE st.push(i) # 去掉哨兵 nums.pop()

性质

• 使栈顶出栈的元素i一定是栈顶元素x的RFG （简单来说这是因为i的右边的非RFG元素没有能力使得i出栈，而还会被算法push入栈成为新栈顶）
• 结合思路1的推论3，栈顶元素x的往下一个元素一定是栈顶元素的LFGE!

延伸: 求严格的RFG和LFG

# 添加哨兵元素，保证所有元素一定会pop出栈 nums.push(inf) for i from 0 -> n-1: while st非空 and nums[st.top] < nums[i]: x = st.pop() RFG[x] = i # 求RFG # 去掉相等左元素 while st非空 and nums[st.top] == nums[x]: st.pop() # 求严格的LFG LFG[x] = st.top if st非空 else -1 st.push(i) # 去掉哨兵 nums.pop()

实战

Leetcode 84

https://leetcode-cn.com/problems/largest-rectangle-in-histogram/

先看题解的暴力解法，再看下面代码就好理解了

classSolution:# 单调栈：# 求每个柱子的：# 左最近 <= heights[x] 的位置# 右最近 < heights[x] 的位置## 从而确定包含柱x的高为 heights[x] 的矩形的最大宽度，最后得出潜在的矩形大小deflargestRectangleArea(self,heights:List[int])->int:# 添加哨兵，保证所有元素最终都会出栈结算heights.append(-float('inf'))n=len(heights)st=[]ans=0foriinrange(n):# 当前元素更小# 栈顶元素找到了右边界whilestandheights[st[-1]]>heights[i]:x=st.pop()# 右最近 < heights[x]rfs=i# 左最近 <= heights[x]lfse=st[-1]ifstelse-1# 确定最大宽度width=rfs-1-(lfse+1)+1# 更新答案ans=max(ans,width*heights[x])# 注意栈中存放的是索引st.append(i)returnans

更多利用单调栈性质相关的题目：

739 每日温度（中等） 暴力解法 + 单调栈
496 下一个更大元素 I（简单） 暴力解法、单调栈
901 股票价格跨度（中等） 「力扣」第 901 题：股票价格跨度（单调栈）

42 接雨水（困难） 暴力解法、优化、双指针、单调栈
581 最短无序连续子数组 单调栈、双指针

以下几题形似单调栈，但没有用到单调栈的性质，而是利用了贪心的思想
402 移掉K位数字
321 拼接最大数
316 去除重复字母（困难）

739 秒杀！

classSolution:defdailyTemperatures(self,temperatures:List[int])->List[int]:# 添加一个哨兵元素，保证所有元素都会出栈temperatures.append(float('inf'))n=len(temperatures)st=[]# 预置答案数组，可以随便初始化ans=[0]*(n-1)# 遍历当前位置foriinrange(n):whilestandtemperatures[st[-1]]<temperatures[i]:x=st.pop()# 右最近 > temperatures[x]rfg=i# 注意需要判断是否触及边界ans[x]=rfg-xifi<(n-1)else0st.append(i)# 删除哨兵temperatures.pop()returnans

581

未完待续…