栈里始终保持递增或递减——靠这一个小规则，把"找右边第一个更大的数"从 O(n²) 降到 O(n)。
有一类常见问题：给一个数组，对每一个数，都要找出它右边第一个比它大的数。最直接的想法是枚举法——对每个数，往右一个个找，直到找到更大的为止。这种写法最坏情况下是 O(n²)（2.1 节讨论过，数据量一大就容易超时）。
单调栈能把这件事优化到 O(n)。它是一种特殊用法的栈：在往栈里塞新数据之前，先把栈顶那些"不再有用"的数据清理掉，让栈里剩下的数据始终保持递增或递减的顺序——这正是"单调"这个名字的来源。
用数组 {3, 1, 4, 1, 5, 9, 2, 6} 演示。维护一个栈，栈里存的是下标，并且要求栈底到栈顶对应的数值递减。从左到右扫描每个数 arr[i]：只要栈顶元素对应的数值比 arr[i] 小，说明栈顶那个数找到了它"右边第一个更大的数"——就是 arr[i] 本身，把栈顶弹出并记录答案；重复这个弹出动作，直到栈顶比 arr[i] 大（或者栈空了）为止，再把 i 压入栈。
| 1 | vector<int> NextGreater(vector<int> arr) |
| 2 | { |
| 3 | int n = arr.size(); |
| 4 | vector<int> result(n, -1); // 默认-1，表示没有找到更大的数 |
| 5 | stack<int> st; // 存下标，栈里的数值保持递减 |
| 6 | |
| 7 | for (int i = 0; i < n; i++) |
| 8 | { |
| 9 | while (!st.empty() && arr[st.top()] < arr[i]) |
| 10 | { |
| 11 | result[st.top()] = arr[i]; // arr[i]就是栈顶元素要找的答案 |
| 12 | st.pop(); |
| 13 | } |
| 14 | st.push(i); |
| 15 | } |
| 16 | return result; |
| 17 | } |
9 和 6 始终没有被弹出——它们右边再也没有比自己更大的数了，对应的答案保持默认值 -1。{4,4,5,5,9,-1,6,-1}。9 是整个数组里最大的数，右边不可能有比它更大的，所以结果是 -1；6 是数组最后一个数，右边没有任何数，同样是 -1。看起来代码里有一层 for 套一层 while，很像两层嵌套循环，容易让人误以为是 O(n²)——但其实不是。关键在于：每个数最多只会被压入栈一次，也最多只会被弹出一次。一旦某个数被弹出，它就再也不会被重新压回栈里了。
n 次入栈操作；而出栈操作的总次数，无论 while 循环在哪些位置触发了多少次，加起来也不可能超过 n 次（因为总共只有 n 个数能被弹出）。所以入栈、出栈两类操作加起来一共最多 2n 次，整体时间复杂度是严格的 O(n)，而不是 O(n²)——这是单调栈类问题里非常经典的"均摊复杂度"分析思路。| 做法 | 核心思路 | 时间复杂度 |
|---|---|---|
| 暴力枚举 | 对每个数，往右逐个找更大的数 | O(n²) |
| 单调栈 | 维护递减的栈，提前清理不再有用的数据 | O(n) |
< 换成 >，就能找"右边第一个更小的数"；把循环方向从左到右改成从右到左，就能找"左边第一个更大/更小的数"。这套"维护单调性、提前清理无用数据"的思路，后面在直方图最大矩形、股票买卖等问题里都会反复出现——掌握了这一节的框架，遇到变体时只需要调整比较条件，不需要重新设计算法。