单调栈：高效解决边界查找问题

一、上期回顾

学完并查集 DSU：初始化、查找、合并、路径压缩，连通块、集合合并类题目直接秒杀。今天攻坚单调栈，属于刷题必备、面试常问的线性时间算法。

二、单调栈核心概念

1. 什么是单调栈

栈内元素保持严格递增 / 严格递减，始终维持单调性。

• 单调递增栈：栈底到栈顶从小到大
• 单调递减栈：栈底到栈顶从大到小

2. 核心作用

以 O (n) 时间，快速找到每个元素左边 / 右边 第一个比它大 / 小的元素普通双重循环是 O (n²)，单调栈一遍遍历 O (n) 搞定。

3. 适用场景

• 下一个更大元素
• 每日温度
• 接雨水
• 柱状图中最大矩形
• 寻找左右边界类问题

三、单调栈工作原理

1. 遍历数组每个元素
2. 栈不为空，且当前元素破坏栈单调性
3. 不断弹出栈顶，同时记录答案
4. 把当前元素压入栈
5. 全程维持栈内单调特性

口诀：不满足单调就弹栈，满足就入栈

四、模板 1：单调递减栈（求下一个更大元素）

题目：给数组，求每个元素右边第一个比自己大的元素

#include <iostream> #include <vector> #include <stack> using namespace std; int main() { vector<int> nums = {2,1,2,4,3}; int n = nums.size(); vector<int> res(n, -1); stack<int> st; // 存下标，保持单调递减 for(int i = 0; i < n; i++) { // 当前元素大于栈顶元素，破坏递减，弹出并更新答案 while(!st.empty() && nums[i] > nums[st.top()]) { int idx = st.top(); st.pop(); res[idx] = nums[i]; } st.push(i); } for(int x : res) cout << x << " "; return 0; }

输出：

4 2 4 -1 -1

五、模板 2：单调递增栈（求下一个更小元素）

只需要改判断条件：

while(!st.empty() && nums[i] < nums[st.top()])

六、经典例题：每日温度

题目：每日温度数组，求每一天需要等几天才会遇到更高温度

vector<int> dailyTemperatures(vector<int>& T) { int n = T.size(); vector<int> ans(n,0); stack<int> st; for(int i = 0; i < n; ++i) { while(!st.empty() && T[i] > T[st.top()]) { int idx = st.top(); st.pop(); ans[idx] = i - idx; } st.push(i); } return ans; }

七、单调栈通用刷题套路

1. 栈中优先存下标，方便计算距离、索引
2. 想要「右边更大」→ 用单调递减栈
3. 想要「右边更小」→ 用单调递增栈
4. 循环条件：不满足单调性就一直弹栈，弹栈时更新答案
5. 最后压入当前下标

八、今日核心总结

1. 单调栈：栈内元素维持递增 / 递减单调性
2. 时间复杂度 O (n)，每个元素入栈一次、出栈一次
3. 核心用途：找左右第一个更大 / 更小元素
4. 刷题固定模板：遍历 + 弹栈更新答案 + 压栈
5. 栈存下标比存数值更灵活，适配所有边界类题目

九、课后练习

1. 手写下一个更大元素代码，理解弹栈逻辑
2. 独立写出每日温度单调栈解法
3. 尝试用单调栈求「左边第一个比自己小的元素」