单调栈基础与模板

单调栈基础

单调递减栈：

• 特性 1：插入元素 ele 时，先和栈顶比较。若更小则入栈；否则持续弹栈。
• 元素弹出时，通常就是它被“结算”的时机。
• 特性 2：若当前栈为 [a, b, c, d]（单调递减），则 c 左侧第一个比 c 大的是 b，b 左侧第一个比 b 大的是 a。

例子：接雨水

维护一个栈（栈顶元素对应高度更小）。遍历数组时，如果新元素 num > 栈顶，说明栈顶位置可以计算：

• 栈顶出栈并计算贡献。
• 当前元素继续参与后续比较。
• 最后将当前下标入栈。

如何判断用递增栈还是递减栈 ^zqyyg3

• 如果要找“左侧第一个更大”，通常用递减栈。
• 如果要找“左侧第一个更小”，通常用递增栈。
• 原因是：弹出栈顶时需要用到“弹出后新的栈顶”，而这个元素一定在当前遍历位置的左侧。