单调栈理解和实战

碎碎念时隔多年又回到了刷题状态对单调栈又有了新的理解这里记录一下作为备忘所要解决的问题通常单调栈用于解决给定数组 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 栈顶元素xpop删除栈顶并开始下一轮比较这里在搜答案的过程中通过pop操作删除备选区中无关的不可能成为后续迭代元素的答案的元素从而避免重复搜索相同元素进而加速后续元素的搜索答案过程2.if 当前元素i 栈顶元素x则找到了当前元素i的RFG (右最近大于元素)为栈顶元素x3.推论由要点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 84https://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))nlen(heights)st[]ans0foriinrange(n):# 当前元素更小# 栈顶元素找到了右边界whilestandheights[st[-1]]heights[i]:xst.pop()# 右最近 heights[x]rfsi# 左最近 heights[x]lfsest[-1]ifstelse-1# 确定最大宽度widthrfs-1-(lfse1)1# 更新答案ansmax(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))nlen(temperatures)st[]# 预置答案数组可以随便初始化ans[0]*(n-1)# 遍历当前位置foriinrange(n):whilestandtemperatures[st[-1]]temperatures[i]:xst.pop()# 右最近 temperatures[x]rfgi# 注意需要判断是否触及边界ans[x]rfg-xifi(n-1)else0st.append(i)# 删除哨兵temperatures.pop()returnans581未完待续…