单调栈

单调栈只保留仍可能被未来元素首次击败、成为未来答案的候选，并让其键值按某方向单调。新元素到来时，所有被它支配且以后不可能更优的栈顶会一次性永久弹出；每个元素最多入栈、出栈各一次，所以看似嵌套的循环总成本线性。关键是明确相等元素的处理，否则“最近严格大于”和“最近大于等于”会混淆。

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

序列 $[2,1,4,3]$ 求右侧第一个更大元素：扫描到 $4$ 时依次弹出 $1,2$，它们答案均为 $4$；$3$ 入栈后至末尾无更大者。直方图最大矩形中，栈保存递增高度及其最早可延伸位置，遇到更矮柱时结算被弹柱的最大宽度。

单调栈只适合答案由邻近支配关系决定的问题，不能替代一般范围最大查询。重复值时使用 < 还是 <= 会影响边界归属；哨兵可统一清空栈，但其值和下标必须不污染真实答案。

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

栈公理库栈Stack · LIFO stack只在同一端插入和删除、遵循后进先出的结构。 提供后进先出候选集，全序公理库全序Total order · Linear order任意两个元素都可比较的偏序。 定义支配，摊还分析公理库摊还分析Amortized analysis对操作序列的总成本作上界，而非逐次最坏成本。 证明 $O(n)$。下一个更大元素、股票跨度、笛卡尔树和直方图面积都共享这一“弹出已失去未来价值元素”的模式。

单调栈扫描数组时维护“栈内下标递增、对应值单调，且尚未找到右侧更小项”的候选不变量。相同弹栈轨迹可在线性时间构造Cartesian Tree公理库笛卡尔树Cartesian tree同时满足下标中序与数组值堆序的唯一二叉树。：最后弹出链成为新节点左子。该树再把RMQ公理库静态区间最值查询（RMQ）Range minimum query · RMQ预处理静态数组后，返回区间最小元素的位置并固定并列规则。转成 LCA。单调栈本身回答一次静态邻近关系，不支持数组更新；Cartesian tree 与 RMQ 也需固定并列规则。