单调栈（Monotonic Stack）：速寻「左右首个最值」的线性利器

一、痛点引入：暴力解法的致命缺陷

在算法刷题中，我们高频遇到一类问题：对数组中每个元素，快速找到它左边/右边第一个比自己大/小的元素。
最直观的暴力枚举法，时间复杂度高达O(n2)O(n^2)O(n2)，面对大数据量直接超时；而单调栈，就是专门解决这类问题的最优工具，仅用O(n)O(n)O(n)线性时间，就能完成所有元素的查询。

二、单调栈核心：本质与规则

1. 定义：栈内从栈底到栈顶始终保持单调递增或单调递减的栈，就是单调栈。
2. 黄金规则：栈中存储数组索引，而非元素值！
   • 索引可直接定位元素值；
   • 索引能快速计算位置差（如天数、下标距离）；
3. 唯一使命：快速查找数组中每个元素的「左/右首个更大/更小元素」
   所有能转化为这个模型的题目，无脑用单调栈！

三、万能解题模板

以栈底 → 栈顶单调性为准：

通用流程：
遍历数组 → 循环判断栈顶是否满足条件 → 满足则弹出栈顶并记录答案 → 不满足则当前索引入栈。

四、实战精讲：两道经典例题

例题1：LeetCode 739. 每日温度

需求：找到每一天下一个更暖和的天数（右侧第一个更大温度的下标差）
→ 场景：找右侧首个更大元素 →维护单调递减栈

classSolution:defdailyTemperatures(self,temperatures:List[int])->List[int]:n=len(temperatures)ans=[0]*n# 初始化答案，无更大温度则为0st=[]# 单调递减栈：栈底到栈顶温度越来越小fori,xinenumerate(temperatures):# 当前温度 > 栈顶温度，说明栈顶找到了右侧第一个更大值whilestandtemperatures[st[-1]]<x:ans[st[-1]]=i-st[-1]# 计算天数差st.pop()# 已找到答案，弹出栈顶st.append(i)# 当前索引入栈，维持递减特性returnans

例题2：LeetCode 1475. 商品折扣后的最终价格

需求：每个商品的折扣 = 右侧第一个小于等于它的价格，最终价=原价-折扣
→ 场景：找右侧首个更小/相等元素 →维护单调递增栈

classSolution:deffinalPrices(self,prices:List[int])->List[int]:st=[]# 单调递增栈：栈底到栈顶价格越来越大fori,xinenumerate(prices):# 当前价格 <= 栈顶价格，栈顶找到右侧第一个更小值whilestandprices[st[-1]]>=x:prices[st[-1]]-=x# 直接计算最终价格st.pop()# 已处理完成，弹出栈顶st.append(i)# 当前索引入栈，维持递增特性returnprices

五、时间复杂度：为什么是 O(n)？

即便代码有while循环嵌套，单调栈依然是线性时间：
数组中每个元素最多入栈1次、出栈1次，总操作数为2n2n2n，常数级忽略后，时间复杂度为O(n)\boldsymbol{O(n)}O(n)。

六、核心口诀

1. 核心场景：找左右首个更大/更小元素；
2. 栈存索引：不存值存下标，方便计算距离；
3. 栈序选择：找大用递减，找小用递增；
4. 时间复杂度：O(n)O(n)O(n)线性最优解。

总结

单调栈是专为「查找首个最值」设计的专用数据结构，只要记住：
往右找更大，维持栈递减；往右找更小，维持栈递增。
识别出题目模型后，直接套用模板即可秒杀。无论是每日温度、商品折扣，还是柱状图最大矩形、接雨水等难题，本质都是单调栈核心场景的延伸。