单调栈：高效解决区间极值问题-编程阁

一、什么是单调栈

单调栈本质：栈内元素保持严格递增或严格递减

单调递增栈：从栈底到栈顶元素越来越大
单调递减栈：从栈底到栈顶元素越来越小

核心作用：快速找每个元素左边 / 右边第一个比它大 / 小的元素普通暴力两层循环 O (n²)，单调栈直接 O (n) 秒杀。

二、单调栈工作规则

以单调递增栈为例：

遍历每个元素
栈不为空，且当前元素破坏递增规则，不断弹出栈顶
弹出时，就找到了被弹出元素的右侧最近更大 / 更小值
把当前元素压入栈
维持栈内单调性不变

三、单调栈通用刷题模板（必背）

// 单调栈通用模板 for(int i = 0; i < n; i++) { // 不满足单调性就一直弹出 while(!st.empty() && nums[i] 满足弹出条件) { // 记录答案：栈顶元素的右侧答案是 nums[i] int top = st.top(); st.pop(); // 业务逻辑处理 } st.push(i); // 存下标，方便计算距离 }

技巧：栈里一般存数组下标，通过下标取值，方便求区间长度。

四、两种单调栈区别

1. 单调递增栈

栈底→栈顶：从小到大适用：找右边第一个比自己小的元素

2. 单调递减栈

栈底→栈顶：从大到小适用：找右边第一个比自己大的元素

五、经典例题：每日温度（LeetCode 739）

题目大意

给定温度数组，对于每一天，求出还要过几天才会出现更高温度；没有填 0。

思路

典型单调递减栈模板题：遍历温度，维持栈内温度递减；遇到比栈顶大的温度，弹出并计算天数差。

完整可运行代码

#include <iostream> #include <vector> #include <stack> using namespace std; vector<int> dailyTemperatures(vector<int>& temperatures) { int n = temperatures.size(); vector<int> res(n, 0); stack<int> st; for(int i = 0; i < n; ++i) { // 破坏递减，开始弹出 while(!st.empty() && temperatures[i] > temperatures[st.top()]) { int idx = st.top(); st.pop(); res[idx] = i - idx; } st.push(i); } return res; } int main() { vector<int> t = {73,74,75,71,69,72,76,73}; vector<int> ans = dailyTemperatures(t); for(int x : ans) { cout << x << " "; } return 0; }