直接回答:单调栈解决“每个元素的左/右侧最近更大/更小元素”类问题,O(n) 一趟扫描:维护一个单调递减(或递增)的栈,新元素入栈前弹出所有违反单调性的元素——被弹出的元素此刻找到了它的“右侧第一个更大者”,栈顶剩余即“左侧最近更大者”。经典题:每日温度、下一个更大元素 I/II、柱状图最大矩形、接雨水(栈解法)。

展开解析:模板要素:栈里存下标不存值(要算距离与位置);遍历方向决定“左最近”还是“右最近”(正序扫弹出时定右侧答案,倒序扫定左侧);单调性方向由问题决定(找更大者用递减栈——栈底到栈顶递减,新元素比栈顶大就弹)。以柱状图最大矩形讲透:对每个柱子,以它为高的最大矩形宽度 = 左侧第一个更矮的位置到右侧第一个更矮的位置之间——两次单调栈(或一次扫描弹出时同时定右边界、栈顶即左边界)得出所有柱子的答案取 max。接雨水的栈理解:每个凹槽在被更高柱子“封口”时结算,弹出时按(当前高度与栈顶高度的较小值 - 凹槽底高)× 宽度累加。变体与延伸:单调队列(滑动窗口最大值,双端队列维护窗口内递减序列)是同一思想在滑动窗口场景的版本;贡献法技巧——“每个元素作为最值支配的区间”类求和题(子数组最小值之和)用单调栈求支配边界再乘贡献,注意相等元素的边界去重(一边取严格一边取非严格)。复杂度直觉:每个元素入栈出栈各一次,摊还 O(n)——这是它替代 O(n²) 枚举的理论根基。

追问方向:单调栈与单调队列的适用场景分界?子数组最值求和的去重细节为什么重要?

(约 490 字)