单调栈 —— 1.基本概念与核心算法

1. 基本概念

1.1 知识预备

在理解单调栈之前，我们需要先掌握两个基础概念：栈（Stack） 和 单调性（Monotonicity）。

什么是栈（Stack）

栈是一种**后进先出（LIFO, Last-In-First-Out）**的数据结构：

• 新元素始终压入栈顶（push）
• 移除元素也始终从栈顶弹出（pop）

我们可以把栈想象成一叠书：

• 你只能从最上面放/取书（栈顶）
• 先放进去的书在下面，必须等上面的书移除后才能访问

基本操作：

• push(x)：将元素 x 压入栈顶
• pop()：弹出栈顶元素
• top()：查看栈顶元素但不弹出
• empty()：判断栈是否为空

1.2 什么是单调栈

单调栈是栈的一种特殊使用方式，其特点是：始终保持栈内元素有序（单调递增或递减）。

常见的两种形式：

• 单调递增栈：栈中元素从栈底到栈顶递增（栈顶最小）
• 单调递减栈：栈中元素从栈底到栈顶递减（栈顶最大）

例如，维护一个单调递增栈的过程：

初始空栈：[]
压入 3： [3]
压入 5： [3, 5] ✅（递增）
压入 2： ❌（2 小于栈顶 5，弹出 5，再比较 3，直到栈递增）最后的结果是 [2]

单调栈的本质：在压入元素时，通过弹出不满足单调性的栈顶元素，从而维护一个有序结构，方便我们高效地找到“下一个更大/小”的元素。

单调栈常解决的问题类型：

适合使用 单调栈 的题目，通常具有以下几个显著特点：

1. 需要找“第一个满足条件的前/后缀元素”

比如：

• 右边第一个比自己大的元素
• 左边第一个比自己小的元素
• 最近的更高温度、更高价格、更大柱子

👉 本质：找某个方向上第一个满足单调性条件的元素

2. 数组或序列题，且有“元素之间的相对关系”

• 题目一般给定一个 一维数组/序列
• 要你找出元素之间的顺序比较关系

例如：

• 每个元素右边第一个更大的数
• 每个元素左边第一个更小的位置

3. 暴力解法是 O(n²)，但可以优化为 O(n)

如果你写出暴力法是两层循环查“后面第一个符合条件的元素”，就可以考虑：

是否能用单调栈来代替嵌套循环

单调栈能做到：

• 每个元素最多被压入一次，弹出一次
• 时间复杂度稳定在 O(n)

4. 问题与“范围”、“跨度”或“影响范围”有关

如：

• 当前元素往左/右能扩展到多远
• 柱状图中每个柱子形成的最大矩形
• 股票价格连续上升/下降天数

这些问题都和某个元素能“影响”多远有关，适合用单调栈维护边界。

1.3 单调栈的常见例题

2. 核心算法

2.1 解题思路（以“下一个更小元素”为例）

• 使用一个栈，从左到右遍历数组
• 当当前元素比栈顶元素小：说明找到“右侧第一个更小元素”
• 栈中维护一个单调递增序列的索引

2.2 代码实现（Python 示例）

def next_smaller_elements(nums):
    res = [-1] * len(nums)
    stack = []
    for i in range(len(nums)):
        while stack and nums[i] < nums[stack[-1]]:
            idx = stack.pop()
            res[idx] = nums[i]
        stack.append(i)
    return res

2.3 灵活应用

3. 总结

对于一个新手而言，单调栈往往是让人感到 amazing 的方法，需要结合题目的特点进行分析，当满足前面提到的某一些特点的时候，可以考虑使用单调栈来解决问题。

单调栈只是一个工具，它甚至不能说是某一种算法。因此有时候考察的可能是单调栈与其他算法的结合，比如 DP 之类的。

这里对本文做个小结：

• 单调栈是一个高效解决序列型“最值查找”问题的利器
• 本质是维护一个具有顺序性质的栈
• 实现时注意：栈中通常存储索引而非值
• 单调栈常作为经典面试题考点，应熟练掌握其基本模板并灵活变形

更多的例子将会结合力扣、洛谷的题目进一步展开，感兴趣的小伙伴们不妨关注一波 ~

感谢各位小伙伴们的 阅读、点赞、评论 与 关注 ~ 希望本文能帮助到各位，共勉 ~

Smileyan
2025.04.12 22:17