单调栈保持栈内元素单调递增或递减，高效解决「下一个更大/小元素」类问题。

单调栈类型

类型	特性	适用场景
单调递增栈	栈底→栈顶递增	找下一个更小元素
单调递减栈	栈底→栈顶递减	找下一个更大元素

构建方法

遍历数组时，将当前元素与栈顶比较：

递增栈：当前元素 < 栈顶 → 弹出栈顶，直到满足单调性
递减栈：当前元素 > 栈顶 → 弹出栈顶，直到满足单调性

示例：构建单调递增栈

数组 [3, 2, 5, 1]：

步骤	操作	栈状态
处理 3	空栈直接入	`[3]`
处理 2	2 < 3，弹出 3，入栈 2	`[2]`
处理 5	5 > 2，直接入栈	`[2, 5]`
处理 1	1 < 5 弹出，1 < 2 弹出，入栈 1	`[1]`

典型应用

下一个更大元素：单调递减栈，弹出时记录结果
移除 K 位数字：单调递增栈，保证数字尽可能小
柱状图最大矩形：单调栈找左右边界

代码模板

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def next_greater_element(nums):
    result = [-1] * len(nums)
    stack = []  # 单调递减栈，存索引

    for i, num in enumerate(nums):
        while stack and num > nums[stack[-1]]:
            idx = stack.pop()
            result[idx] = num
        stack.append(i)

    return result

时间复杂度 O(n)，每个元素最多入栈出栈各一次。

单调栈类型

构建方法

示例：构建单调递增栈

典型应用

代码模板

Comments