单调栈把一类O(n²)问题降到O(n)——识别模式是面试分水岭。
定义：栈里元素单调递增或递减。压入前弹出破坏单调的元素。
下一个更大：遍历nums；stack.top<=nums[i]时弹出并记nums[i]为其答案。压入nums[i]。遍历完栈里剩的无下一个更大。
直方图最大矩形：对每根柱子找左右第一个比它低的。单调递增栈一次扫描。
模式："对每个元素找左/右最近更大/更小"→单调栈。
均摊O(n)因为每个元素进出栈各一次。
单调栈就是压入前弹掉破坏单调的元素。"下一个更大"：遍历数组，stack.top<=当前就弹出——当前就是它的答案。压入当前。结尾栈里剩的没下一个更大。整体O(n)因为每个下标恰好进出一次——经典均摊。模式识别：问题只要是"每个i左边/右边最近满足P的j"就试单调栈。"每日温度"、"直方图最大矩形"、"接雨水"、"移除k位让结果最小"都是同一形状。
要位置/距离就在栈里存下标不存值。
"前一个更小"换方向；"下一个更小"换比较符。
即答侠给了模板+6种变形——见过一次形状，后面全是1:1。
相关但不同。单调队列（deque）支持从另一端删——滑动窗口最大值用它。
问题不是"最近满足P"时——比如"第k大"要堆不是单调栈。