形式陈述

扫描序列时维护索引栈，使对应值单调。加入新元素前，反复弹出不再可能成为后续答案的栈顶；每个元素至多入栈一次、出栈一次，因此总时间 $O(n)$。 具体严格/非严格比较决定处理相等元素的规则，必须与“最近更大/更小”的定义一致。

直觉

栈中只保留仍可能被未来元素首次击败的候选；一旦新元素证明某候选已失去资格，就永久删除。

例子与边界

可在线性时间求每个位置左/右侧最近更小元素、柱状图最大矩形。相等元素若处理不一致，会导致重复边界或错误区间。

推论与应用

它是摊还分析的简洁范例，并连接 Cartesian tree、区间贡献计数和凸包式候选淘汰。

参考资料

• OI-Wiki contributors, OI-Wiki (2026), monotonic stack.
• Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, 4th ed. (2022), stack-based amortized patterns.