单调栈(Monotonic Stack)

定义

单调栈(Monotonic Stack)不是新的存储结构,而是一种栈的使用范式:在入栈前弹出所有破坏单调性的元素,使栈内元素自底向上保持单调递增或递减。

原理

以"下一个更大元素"问题为例:从左到右扫描,维护单调递减栈;当前元素大于栈顶时,栈顶元素的答案就是当前元素,弹出并继续比较。每个元素恰好入栈出栈各一次,总复杂度 O(n)。弹出时机蕴含的信息(左右第一个更大/更小元素)是解题关键。

应用

经典问题包括:下一个更大元素、每日温度、柱状图中最大矩形、接雨水、最大全 1 子矩形(逐行转化为柱状图)、去除重复字母求字典序最小结果等;编译器表达式求值中的算符优先处理也有类似结构。单调队列则是同一思想在滑动窗口最值上的应用。

优缺点

优点是把一类看似 O(n^2) 的"最近更大/更小元素"问题降到 O(n),代码短;局限是仅适用于扫描过程中旧元素可被安全淘汰的问题形态,建模需要一定经验。