1. 单调栈：算法竞赛与面试中的高效解题利器
在算法竞赛和编程面试中，单调栈是一种极其高效且实用的数据结构。它通过维护栈内元素的单调性，能够在O(n)时间复杂度内解决一系列看似复杂的问题。我第一次接触单调栈是在解决LeetCode第84题"柱状图中最大的矩形"时，当时暴力解法超时让我意识到必须寻找更优解，而单调栈正是那把钥匙。
单调栈的核心思想很简单：在遍历数组时，维护一个栈结构，保证栈内元素始终保持单调递增或单调递减的顺序。这种结构特别适合解决"寻找下一个更大/更小元素"这类问题。在实际应用中，单调栈可以高效解决四大类问题：
- 寻找下一个更大/更小元素
- 计算柱状图最大矩形面积
- 处理滑动窗口极值问题
- 解决某些特殊的动态规划问题
2. 单调栈的核心原理与实现步骤
2.1 单调栈的基本性质
单调栈有两种基本形式：
- 单调递增栈：栈底到栈顶元素值递增
- 单调递减栈：栈底到栈顶元素值递减
选择哪种单调性取决于具体问题：
- 当需要找"下一个更大元素"时，使用单调递增栈
- 当需要找"下一个更小元素"时，使用单调递减栈
关键提示：单调栈中通常存储数组索引而非元素值，因为索引可以同时提供位置和值信息，这在计算距离、面积等问题时非常有用。
2.2 单调栈的通用实现模板
以下是单调栈的Python通用实现模板：
def monotonic_stack(nums): stack = [] # 存储索引 result = [0] * len(nums) # 存储结果 for i in range(len(nums)): # 维护栈的单调性 while stack and nums[i] > nums[stack[-1]]: # 这里决定递增/递减 top_idx = stack.pop() # 处理弹出的元素 result[top_idx] = i - top_idx # 根据问题调整 stack.append(i) # 处理栈中剩余元素 while stack: top_idx = stack.pop() result[top_idx] = -1 # 或根据问题需求赋值 return result2.3 单调栈的四步解题法
根据多年刷题经验，我总结出使用单调栈的四步解题法：
确定栈的单调性：
- 明确问题要找的是"更大"还是"更小"元素
- 找更大元素→单调递增栈；找更小元素→单调递减栈
确定栈中存储内容：
- 90%情况下存储索引更优
- 特殊情况下可能需要存储值或复合数据
设计弹栈处理逻辑：
- 这是解题的核心，不同问题处理方式不同
- 可能需要计算距离、面积、或更新结果数组
处理剩余元素：
- 遍历结束后栈中可能还有未处理元素
- 根据问题要求给这些元素赋默认值
3. 经典问题实战解析
3.1 下一个更大元素问题（LeetCode #496）
问题重述
给定两个数组nums1和nums2，其中nums1是nums2的子集。对于nums1中的每个元素，找到它在nums2中对应位置右侧的第一个更大元素。
解法分析
这道题有两种解法：
- 暴力法：时间复杂度O(m*n)
- 单调栈法：时间复杂度O(m+n)
单调栈解法思路：
- 预处理nums2，使用单调栈找到每个元素的下一个更大元素
- 将结果存入哈希表便于快速查询
- 遍历nums1直接从哈希表获取结果
优化后的代码实现
class Solution: def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]: stack = [] next_greater = {} # 逆序遍历更容易理解 for num in reversed(nums2): while stack and num >= stack[-1]: stack.pop() next_greater[num] = stack[-1] if stack else -1 stack.append(num) return [next_greater[num] for num in nums1]复杂度分析：
- 时间复杂度：O(m+n)，其中m是nums1长度，n是nums2长度
- 空间复杂度：O(n)，用于存储哈希表和栈
3.2 每日温度问题（LeetCode #739）
问题重述
给定每日温度数组，返回一个数组表示需要等待多少天才能遇到更高温度。
解法分析
这是典型的"下一个更大元素"变种，需要计算的是天数差而非元素值。
关键点：
- 使用单调递减栈
- 栈中存储索引以便计算天数差
- 遇到更高温度时更新结果数组
代码实现与注释
class Solution: def dailyTemperatures(self, T: List[int]) -> List[int]: n = len(T) res = [0] * n stack = [] # 存储索引 for i in range(n): # 当前温度比栈顶温度高时 while stack and T[i] > T[stack[-1]]: prev_idx = stack.pop() res[prev_idx] = i - prev_idx # 计算天数差 stack.append(i) return res实战技巧：
- 逆序遍历也可以解决这个问题，但正序更直观
- 初始化结果数组为0，这样未处理的元素自动为0
- 存储索引而非温度值，便于计算天数差
3.3 柱状图中最大矩形（LeetCode #84）
问题重述
给定柱状图的高度数组，求能勾勒出的最大矩形面积。
解法分析
这是单调栈的经典应用，关键在于找到每根柱子左右第一个比它矮的柱子。
解题思路：
- 使用单调递增栈
- 遍历时维护栈的递增性
- 当遇到较矮柱子时，计算弹出柱子的最大面积
- 面积计算公式：高度×宽度(右边界-左边界-1)
优化后的代码实现
class Solution: def largestRectangleArea(self, heights: List[int]) -> int: heights = [0] + heights + [0] # 添加哨兵 stack = [] max_area = 0 for i in range(len(heights)): while stack and heights[i] < heights[stack[-1]]: h = heights[stack.pop()] w = i - stack[-1] - 1 max_area = max(max_area, h * w) stack.append(i) return max_area关键优化点：
- 添加哨兵节点简化边界处理
- 一次遍历同时确定左右边界
- 在弹栈时即时计算面积
经验分享：这个问题我最初用暴力法提交时超时了，后来发现单调栈解法的时间复杂度从O(n²)降到O(n)，性能提升显著。这也是单调栈强大之处的典型例证。
4. 单调栈的高级应用与技巧
4.1 处理环形数组问题
有些问题如LeetCode #503（下一个更大元素II）涉及环形数组。解决方法是将数组翻倍，然后用单调栈处理。
class Solution: def nextGreaterElements(self, nums: List[int]) -> List[int]: n = len(nums) res = [-1] * n stack = [] for i in range(2 * n): while stack and nums[i % n] > nums[stack[-1]]: res[stack.pop()] = nums[i % n] if i < n: stack.append(i) return res4.2 二维矩阵中的单调栈应用
单调栈也可以扩展到二维问题，如LeetCode #85（最大矩形）。解法是将二维问题转化为一系列柱状图问题，然后使用单调栈求解。
4.3 常见错误与调试技巧
在实现单调栈时，容易犯以下错误：
- 混淆单调递增和单调递减栈
- 忘记处理栈中剩余元素
- 边界条件处理不当（如空栈访问）
调试建议：
- 打印栈状态和中间结果
- 用小例子手动模拟算法过程
- 特别注意索引越界问题
5. 单调栈的复杂度分析与适用场景
5.1 时间复杂度分析
单调栈的典型时间复杂度为O(n)，因为：
- 每个元素最多入栈一次、出栈一次
- 即使有嵌套循环，总操作次数也是2n次
5.2 空间复杂度分析
空间复杂度一般为O(n)，主要用于：
- 存储栈结构
- 存储结果数组
5.3 适用问题特征
适合用单调栈解决的问题通常具有以下特征：
- 需要寻找下一个更大/更小元素
- 需要计算基于元素位置的面积或距离
- 问题可以转化为寻找边界的问题
5.4 不适用场景
以下情况可能不适合使用单调栈：
- 需要随机访问历史数据
- 问题与元素顺序无关
- 数据量非常小，暴力法足够
6. 单调栈的变种与扩展
6.1 单调队列
单调队列是单调栈的扩展，可以在两端操作，适用于滑动窗口问题。
6.2 带权值的单调栈
某些问题需要在栈中存储额外信息，如累积和或其他统计量。
6.3 多维度单调栈
处理更复杂的问题时，可能需要同时维护多个单调栈。
在实际刷题过程中，我发现单调栈的掌握需要大量练习。建议从简单题开始，逐步过渡到难题，同时注意总结各类问题的共性和特性。我个人的练习路线是：#496 → #739 → #503 → #84 → #85，由浅入深，循序渐进。
