单调栈
单调栈适合在一次扫描中解决“某一侧最近的更大或更小元素”问题：栈里只保留仍可能成为答案的候选项。本课使用递减栈解决“右侧第一个更大元素”：对每个下标，寻找它右边第一个严格更大的值。时间复杂度是 O(n)，额外空间最坏为 O(n)。
代码里虽然有嵌套的 while，但并不会变成 O(n²)。每个下标只会压栈一次，并且最多弹栈一次。整个扫描最多发生 n 次 push 和 n 次 pop，因此总栈操作不超过 2n。
单调栈如何工作
栈中保存的是下标。这样既能通过 nums[index] 进行比较，也能在找到答案时直接写入 answer[index]。
递减栈从栈底到栈顶保持非递增。扫描到 nums[i] 时，只要当前值严格大于栈顶值，就不断弹出：
while stack and nums[stack[-1]] < nums[i]:
j = stack.pop()
answer[j] = nums[i]
stack.append(i)
为什么当前值一定是被弹出下标的“右侧第一个”更大值？因为这个下标从进入栈开始，一直经过中间所有位置都没有被弹出，说明中间任何值都不够大。直到当前值到来，条件第一次成立。
比较必须使用严格的 <。相等并不属于“更大”，所以两个相等值可以同时留在栈中。
什么时候使用单调栈
看到这样的模式时，可以优先想到单调栈：每个位置都在询问某一侧最近的更大或更小值。它往往能把对每个位置向外重复查找，改成一次线性扫描。
典型应用包括：
- 每日温度： 求还要等多少天才会出现更高温度。
- 股票跨度： 求每个价格左侧最近的更大边界。
- 柱状图中最大的矩形： 求每根柱子左右两侧最近的更小边界。
当结果不只是匹配值时，应保存下标。弹栈时只需改变写回内容，同一套栈就可以得到匹配值、匹配下标或两者之间的距离。
单调栈逐步演示
默认输入是：
nums = [2, 1, 5, 3, 4]
答案初始为 [-1, -1, -1, -1, -1]。没有遇到右侧更大值的位置最终保留 -1。
- i = 0，current = 2。 栈为空，压入下标 0。栈中数值为
[2]。 - i = 1，current = 1。 比较 2 与 1，
2 < 1为假，不弹栈。压入下标 1，栈值成为[2, 1]。 - i = 2，current = 5。 栈顶 1 小于 5，弹出下标 1，写入
answer[1] = 5。 - 仍然使用同一个 current = 5 检查新的栈顶 2。
2 < 5仍为真，弹出下标 0，写入answer[0] = 5。 - 栈已经为空，压入下标 2，栈值为
[5]。 - i = 3，current = 3。
5 < 3为假，压入下标 3，栈值为[5, 3]。 - i = 4，current = 4。
3 < 4为真，弹出下标 3，写入answer[3] = 4。 - 新的栈顶 5 不小于 4，所以停止弹栈，压入下标 4。栈值为
[5, 4]。 - 扫描结束。下标 2 和 4 右侧没有更大值，因此保留
-1。
最终结果是：
answer = [5, 5, -1, 4, -1]
动画把一次成功的循环拆成 compare → pop → resolve 三个独立节拍：先判断，再改变栈，最后写答案。这样暂停在任意一帧时，看到的状态都能对应真实算法中的一个明确动作。
为什么嵌套循环仍是 O(n)
| 情况 | 时间 | 空间 |
|---|---|---|
| 所有输入 | O(n) | O(n) |
for 里嵌着 while，时间复杂度仍是线性。长度为 n 的数组中，每个下标都会在处理自己时 push 一次，因此 push 总数恰好是 n。
一个下标一旦 pop，就永久离开栈，之后不可能再次被 pop。所以 pop 总数最多也是 n。
因此总操作满足：
- pushes = n；
- pops ≤ n；
- pushes + pops ≤
2n。
某一个 current 可能触发多次 pop，但这些 pop 消耗的是以后永远不会重新出现的栈元素。这就是摊还分析：单步可能较贵，整个序列仍然是线性的。
额外空间最坏为 O(n)。严格递减输入如 [6, 5, 4, 3, 2, 1] 在扫描过程中一次也不会弹栈，所有下标都会留在栈里。
边界情况
严格递增
[1, 2, 3, 4, 5] 中，每个新值都会弹出前一个栈顶，结果为 [2, 3, 4, 5, -1]，栈始终很浅。
严格递减
[5, 4, 3, 2, 1] 中没有任何 current 比栈顶大，因此没有 pop，最终所有答案都是 -1。这是栈空间最大的情况。
重复值
对于 [2, 2, 3]，第二个 2 不会弹出第一个 2，因为 2 < 2 为假。3 到来时会依次弹出两个 2，结果是 [3, 3, -1]。
右侧没有更大值
扫描结束后仍在栈里的下标不是错误，它们只是从未遇到更大值。初始化时的 -1 正好就是最终答案。
常见错误
把 while 写成 if
这是最关键的错误。默认例子中，栈值为 [2, 1]、current = 5 时，如果只执行一次 if，只能弹出 1，值 2 的下标会错误地留在栈里。一个 current 可能同时解决多个等待下标，因此必须连续弹栈。
把 < 写成 <=
这会把“严格更大”偷偷改成“更大或相等”，重复值会互相解决，题意已经改变。
只存值、不存下标
只存值可以比较，却不知道应该更新 answer 的哪一个位置。保存下标可以同时得到比较值和写入目标。
说成“严格递减栈”
因为比较条件是严格 <，相等值不会互相弹出，所以精确的不变量是“从底到顶非递增”。只有输入值互不相同时，看起来才是严格递减。
看到嵌套循环就判断 O(n²)
复杂度要按元素生命周期计算。每个下标只进入一次、离开最多一次，动画终局的 lifetime 行和 work meter 会把这笔摊还账直接展开。