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

一、上期回顾学完并查集 DSU初始化、查找、合并、路径压缩连通块、集合合并类题目直接秒杀。今天攻坚单调栈属于刷题必备、面试常问的线性时间算法。二、单调栈核心概念1. 什么是单调栈栈内元素保持严格递增 / 严格递减始终维持单调性。单调递增栈栈底到栈顶从小到大单调递减栈栈底到栈顶从大到小2. 核心作用以 O (n) 时间快速找到每个元素左边 / 右边 第一个比它大 / 小的元素普通双重循环是 O (n²)单调栈一遍遍历 O (n) 搞定。3. 适用场景下一个更大元素每日温度接雨水柱状图中最大矩形寻找左右边界类问题三、单调栈工作原理遍历数组每个元素栈不为空且当前元素破坏栈单调性不断弹出栈顶同时记录答案把当前元素压入栈全程维持栈内单调特性口诀不满足单调就弹栈满足就入栈四、模板 1单调递减栈求下一个更大元素题目给数组求每个元素右边第一个比自己大的元素#include iostream #include vector #include stack using namespace std; int main() { vectorint nums {2,1,2,4,3}; int n nums.size(); vectorint res(n, -1); stackint 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()])六、经典例题每日温度题目每日温度数组求每一天需要等几天才会遇到更高温度vectorint dailyTemperatures(vectorint T) { int n T.size(); vectorint ans(n,0); stackint 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; }七、单调栈通用刷题套路栈中优先存下标方便计算距离、索引想要「右边更大」→ 用单调递减栈想要「右边更小」→ 用单调递增栈循环条件不满足单调性就一直弹栈弹栈时更新答案最后压入当前下标八、今日核心总结单调栈栈内元素维持递增 / 递减单调性时间复杂度 O (n)每个元素入栈一次、出栈一次核心用途找左右第一个更大 / 更小元素刷题固定模板遍历 弹栈更新答案 压栈栈存下标比存数值更灵活适配所有边界类题目九、课后练习手写下一个更大元素代码理解弹栈逻辑独立写出每日温度单调栈解法尝试用单调栈求「左边第一个比自己小的元素」