直接回答:单调栈解决“下一个/上一个更大(更小)元素”家族问题:对每个元素找它右侧第一个比它大的位置、以某元素为最值的区间边界。套路:维护一个从栈底到栈顶单调的栈,新元素入栈前把破坏单调性的栈顶弹出——被弹出者的“下一个更大元素”就是当前元素,每个元素恰入栈出栈一次,总复杂度 O(n)。

展开解析:识别信号:题目出现“第一个更大”“能看到的范围”“以它为最小值的子数组”字样,或暴力解法是“对每个位置向两侧扫描”(O(n²))且扫描具有传递性。典型题族:每日温度/下一个更大元素(模板本体);柱状图最大矩形(以每根柱为高的左右边界);接雨水(单调栈写法,虽然双指针更省空间);滑动窗口最大值用单调队列(deque 变体,队头出窗即删);子数组最小值之和(贡献法 + 单调栈求每个元素的控制区间,注意相等元素边界去重——一侧严格一侧不严格)。实现细节:栈里存下标不存值(值通过下标查,区间计算要用下标);弹栈循环写成 while 比较当前与栈顶;哨兵元素(末尾补 -∞/0)可以免去清空残栈的尾巴逻辑。延伸认知:单调栈本质是“在线维护候选集,淘汰永远不可能成为答案的元素”,与单调队列、并查集离线处理同属“淘汰法”思想;面试中讲清楚“为什么被弹出的元素不可能再成为别人的答案”就是正确性证明的钥匙。

追问方向:循环数组的下一大元素怎么处理?贡献法题目中相等元素为何要两侧不对称?

(约 470 字)