单调栈是一类套路：栈里的元素（或它们对应的值）始终保持单调，新元素入栈前把破坏单调性的元素都弹掉。最经典的应用是 “下一个更大元素”：对数组每个位置 i，求右边第一个比 a[i] 大的值。
思路
维护一个栈，里面存的是还没找到答案的索引，对应的值从底到顶严格递减。每来一个新元素 a[i]：
- 只要栈顶对应的值
a[top] < a[i]，就把它弹出来——它的”下一个更大元素”就是当前的a[i] - 反复弹直到栈顶 ≥
a[i]或者栈空 - 把
i压栈
扫完之后，栈里剩下的索引右边没有更大元素，输出 -1。
关键看法：每个索引最多入栈一次、出栈一次。总操作 O(n)。如果不用栈，每个位置都向右扫一遍就是 O(n²)。
复杂度
- 时间：O(n)
- 空间：O(n)（栈最大装 n 个）
在动画里看什么
- 深蓝：当前正在处理的
a[i]；暖红：刚刚被弹出栈（已经找到答案）的位置；绿色：已经填好答案；浅蓝：还在栈中等待 - 数组下方是
out数组，初始全-1，被解决的位置填进对应的值 - 底部的
stack展示栈内容，深蓝色的是栈顶；可以观察到值始终从底到顶递减