马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。
您需要 登录 才可以下载或查看，没有账号？立即注册
×
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 单调栈的常见例题
应用方向示例标题分析找近来更大/小元素LeetCode 496（下一个更大元素）线性替换暴力嵌套循环求区间最值相干LeetCode 84（柱状图最大矩形）栈维护高度索引序列分析LeetCode 739（逐日温度）找出等待更高温度的天数股票分析LeetCode 901（股票代价跨度）求比当前代价小的近来时间隔断
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 机动应用
变体需求应对计谋查找前一个更小/更大元素从右往左扫描须要记载间隔而不是值栈中存索引，利用 i - stack[-1]找全部区间贡献与前一个/后一个满足条件元素组合出区间
3. 总结
对于一个新手而言，单调栈每每是让人感到 amazing 的方法，须要联合标题的特点举行分析，当满足前面提到的某一些特点的时间，可以思量利用单调栈来办理题目。
单调栈只是一个工具，它乃至不能说是某一种算法。因此偶尔间观察的大概是单调栈与其他算法的联合，好比 DP 之类的。
这里对本文做个小结：
- 单调栈是一个高效办理序列型“最值查找”题目的利器
- 本质是维护一个具有序次性子的栈
- 实现时留意：栈中通常存储索引而非值
- 单调栈常作为经典口试题考点，应纯熟把握其根本模板并机动变形
更多的例子将会结协力扣、洛谷的标题进一步睁开，感爱好的小同伴们不妨关注一波 ~
感谢各位小同伴们的 阅读、点赞、批评 与 关注 ~ 渴望本文能资助到各位，共勉 ~
Smileyan
2025.04.12 22:17
|
发表于 2025-9-28 15:19:30