1. 为什么单调栈每个元素最多入栈出栈一次，从而整体 O(n)
问题
为什么单调栈算法中每个元素最多被入栈和出栈各一次，从而使得整体时间复杂度为 O(n)？
考察点
- 单调栈的线性复杂度证明
- 状态空间与出入栈操作次数的关系
- 摊还分析：虽然单元素可能停留很久，但 push/pop 总次数为 2n，均摊到每个元素为常数时间
答案
单调栈的核心是维护一个元素在栈内保持单调有序的栈。在算法执行过程中，每个元素只会被压入栈一次（入栈时），也只会被弹出一次（当它破坏了单调性被后续元素弹出时）。弹出一个元素后它就不再回到栈中，因此全过程中每个元素至多经历一次 push 和一次 pop，总操作次数为 O(n)，所以整体复杂度是 O(n)。这不依赖每个元素入栈后停留多久，只取决于"每个元素只进出一次"这一事实。
解析
这是摊还分析（amortized analysis）的典型例子。虽然单个元素可能在栈中停留较久，但把全部 push/pop 操作数加起来得到的总量是 2n，均摊到每个元素上就是常数时间，因此整体线性。这也是单调栈与暴力嵌套循环（O(n²)）的本质区别——暴力不断重复扫描，而单调栈每个元素只被看一次。
示例代码
// Next Greater Element 的单调栈骨架
int[] nextGreater(int[] nums) {
int n = nums.length;
int[] res = new int[n];
Deque<Integer> stack = new ArrayDeque<>(); // 存下标
for (int i = n - 1; i >= 0; i--) { // 从右往左
while (!stack.isEmpty() && nums[stack.peek()] <= nums[i]) {
stack.pop(); // 每个元素最多被 pop 一次
}
res[i] = stack.isEmpty() ? -1 : nums[stack.peek()];
stack.push(i); // 每个元素最多被 push 一次
}
return res;
}