单调栈全面解析
一、单调栈的核心概念
1. 什么是单调栈？
定义：栈中元素保持单调性（单调递增或单调递减）
核心思想：利用栈的LIFO特性，维护元素的单调关系
主要用途：解决"下一个更大/更小元素"、"最近更大/更小值"等问题
2. 单调栈的两种类型
# 1. 单调递增栈（栈底到栈顶递增）
# 用途：寻找下一个更小的元素
stack = [] # 栈底小，栈顶大
# 2. 单调递减栈（栈底到栈顶递减）
# 用途：寻找下一个更大的元素
stack = [] # 栈底大，栈顶小二、单调栈通用模板
模板1：下一个更大元素（单调递减栈）
def next_greater_element(nums):
"""
返回每个元素的下一个更大元素的索引
时间复杂度：O(n)
"""
n = len(nums)
result = [-1] * n # 初始化结果为-1
stack = [] # 单调递减栈
for i in range(n):
# 当前元素大于栈顶元素时，栈顶元素的下一个更大元素就是当前元素
while stack and nums[stack[-1]] < nums[i]:
idx = stack.pop()
result[idx] = i
stack.append(i)
return result
# 示例
nums = [2, 1, 2, 4, 3]
# 下一个更大元素的索引: [3, 2, 3, -1, -1]模板2：下一个更小元素（单调递增栈）
def next_smaller_element(nums):
"""
返回每个元素的下一个更小元素的索引
"""
n = len(nums)
result = [-1] * n
stack = [] # 单调递增栈
for i in range(n):
# 当前元素小于栈顶元素时，栈顶元素的下一个更小元素就是当前元素
while stack and nums[stack[-1]] > nums[i]:
idx = stack.pop()
result[idx] = i
stack.append(i)
return result
# 示例
nums = [2, 1, 2, 4, 3]
# 下一个更小元素的索引: [1, -1, -1, 4, -1]模板3：前后两个方向查找（最常用）
def left_right_smaller(nums):
"""
返回每个元素的左右第一个较小值的索引
这是原代码中使用的模式
"""
n = len(nums)
left = [-1] * n
right = [-1] * n
# 找左边第一个较小值
stack = []
for i in range(n):
while stack and nums[stack[-1]] >= nums[i]:
stack.pop()
left[i] = stack[-1] if stack else -1
stack.append(i)
# 找右边第一个较小值
stack.clear()
for i in range(n-1, -1, -1):
while stack and nums[stack[-1]] >= nums[i]:
stack.pop()
right[i] = stack[-1] if stack else -1
stack.append(i)
return left, right三、单调栈的使用技巧
技巧1：处理相等元素
# 1. 严格大于/小于（跳过相等）
while stack and nums[stack[-1]] < nums[i]: # 严格小于
stack.pop()
# 2. 大于等于/小于等于（包含相等）
while stack and nums[stack[-1]] <= nums[i]: # 包含等于
stack.pop()
# 根据题目要求选择：
# - 找"第一个"较小/较大值：使用严格比较
# - 找"最近"的较小/较大值：可能包含等于技巧2：存储索引 vs 存储值
python
# 推荐存储索引：可以获得更多信息
stack.append(i) # 存储索引
# 优点：
# 1. 可以通过索引访问原数组的值
# 2. 可以计算距离、跨度等信息
# 3. 便于处理结果数组技巧3：循环数组的处理
def next_greater_circular(nums):
"""
循环数组中的下一个更大元素
"""
n = len(nums)
result = [-1] * n
stack = []
# 遍历两遍数组模拟循环
for i in range(2 * n):
idx = i % n
while stack and nums[stack[-1]] < nums[idx]:
prev_idx = stack.pop()
result[prev_idx] = nums[idx]
# 只在第一遍遍历时入栈
if i < n:
stack.append(idx)
return result
# 示例
nums = [1, 2, 1]
# 输出: [2, -1, 2]LeetCode单调栈经典题目详解
一、基础入门题（必刷）
1. 739. 每日温度 ⭐⭐
题目：给定每天的温度，返回需要等待多少天才能有更高的温度
def dailyTemperatures(temperatures):
n = len(temperatures)
answer = [0] * n
stack = [] # 单调递减栈（存索引）
for i in range(n):
while stack and temperatures[stack[-1]] < temperatures[i]:
prev_idx = stack.pop()
answer[prev_idx] = i - prev_idx
stack.append(i)
return answer
# 示例
# 输入: [73,74,75,71,69,72,76,73]
# 输出: [1,1,4,2,1,1,0,0]关键点：
单调递减栈（找更高温度）
结果 = 当前索引 - 栈顶索引
2. 496. 下一个更大元素 I ⭐
题目：nums1 是 nums2 的子集，找到 nums1 中每个元素在 nums2 中的下一个更大元素
def nextGreaterElement(nums1, nums2):
next_greater = {}
stack = [] # 单调递减栈
# 为nums2所有元素找到下一个更大元素
for num in nums2:
while stack and stack[-1] < num:
next_greater[stack.pop()] = num
stack.append(num)
# 栈中剩余元素没有下一个更大元素
for num in stack:
next_greater[num] = -1
return [next_greater[num] for num in nums1]
# 示例
# nums1 = [4,1,2], nums2 = [1,3,4,2]
# 输出: [-1,3,-1]变种：
503. 下一个更大元素 II（循环数组）
556. 下一个更大元素 III
二、进阶应用题
3. 84. 柱状图中最大的矩形 ⭐⭐⭐⭐
题目：给定柱状图的高度，求能勾勒出的最大矩形的面积
def largestRectangleArea(heights):
heights.append(0) # 哨兵，确保所有柱子都会被处理
stack = [] # 单调递增栈
max_area = 0
for i in range(len(heights)):
# 当前柱子小于栈顶柱子高度
while stack and heights[stack[-1]] > heights[i]:
h = heights[stack.pop()]
# 宽度计算：如果栈为空，说明左边所有柱子都更高
w = i if not stack else i - stack[-1] - 1
max_area = max(max_area, h * w)
stack.append(i)
heights.pop() # 恢复原数组
return max_area
# 示例
# 输入: [2,1,5,6,2,3]
# 输出: 10 (高度5,6对应的柱子)算法思路：
维护单调递增栈
遇到递减柱子时，计算以栈顶柱子为高的最大矩形
宽度 = 当前索引 - 栈顶下一个索引 - 1
可视化理解：
高度: [2, 1, 5, 6, 2, 3]
索引: 0 1 2 3 4 5
以高度5为例：
左边第一个小于5的是索引1（高度1）
右边第一个小于5的是索引4（高度2）
宽度 = 4 - 1 - 1 = 2
面积 = 5 * 2 = 104. 42. 接雨水 ⭐⭐⭐⭐
题目：给定表示高度的非负整数数组，计算能接多少雨水
def trap(height):
stack = [] # 单调递减栈，存储索引
water = 0
for i in range(len(height)):
# 当前高度大于栈顶高度，形成凹槽
while stack and height[stack[-1]] < height[i]:
bottom = stack.pop() # 凹槽底部
if not stack: # 没有左边界
break
left = stack[-1] # 左边界
h = min(height[left], height[i]) - height[bottom]
w = i - left - 1
water += h * w
stack.append(i)
return water
# 示例
# 输入: [0,1,0,2,1,0,1,3,2,1,2,1]
# 输出: 6两种解法对比：
三、变形与组合题
5. 85. 最大矩形 ⭐⭐⭐⭐
题目：给定仅包含 0 和 1 的二维矩阵，找出只包含 1 的最大矩形
def maximalRectangle(matrix):
if not matrix:
return 0
m, n = len(matrix), len(matrix[0])
heights = [0] * n
max_area = 0
for i in range(m):
# 更新高度数组
for j in range(n):
if matrix[i][j] == '1':
heights[j] += 1
else:
heights[j] = 0
# 使用84题的单调栈解法
max_area = max(max_area, largestRectangleArea(heights))
return max_area
# 需要84题的largestRectangleArea函数转换思路：
将二维问题转化为一维柱状图问题
每一行作为柱状图的底部
高度 = 连续1的个数
6. 901. 股票价格跨度 ⭐⭐
题目：设计一个算法，计算股票当前价格的价格跨度（当前价格小于或等于今天价格的最大连续日数）
class StockSpanner:
def __init__(self):
self.stack = [] # 单调递减栈，存储(价格, 跨度)
def next(self, price: int) -> int:
span = 1
# 合并小于等于当前价格的跨度
while self.stack and self.stack[-1][0] <= price:
_, prev_span = self.stack.pop()
span += prev_span
self.stack.append((price, span))
return span
# 示例
# 输入: [100, 80, 60, 70, 60, 75, 85]
# 输出: [1, 1, 1, 2, 1, 4, 6]创新点：
栈中存储
(价格, 跨度)对利用单调栈合并跨度
7. 402. 移掉K位数字 ⭐⭐⭐
题目：给定一个数字字符串，移除k位数字，使剩下的数字最小
def removeKdigits(num, k):
stack = [] # 单调递增栈
for digit in num:
# 维护单调递增栈，但可以删除k次
while k > 0 and stack and stack[-1] > digit:
stack.pop()
k -= 1
stack.append(digit)
# 如果还有k可以删除，从末尾删除
stack = stack[:-k] if k else stack
# 去除前导零
result = ''.join(stack).lstrip('0')
return result if result else '0'
# 示例
# 输入: num = "1432219", k = 3
# 输出: "1219"贪心策略：
尽可能让高位数字小
维护单调递增栈，遇到递减就删除
四、困难级别挑战题
8. 316. 去除重复字母 ⭐⭐⭐
题目：去除字符串中重复字母，使每个字母只出现一次，且返回结果的字典序最小
def removeDuplicateLetters(s):
last_occurrence = {c: i for i, c in enumerate(s)}
stack = [] # 单调递增栈
seen = set()
for i, c in enumerate(s):
if c in seen:
continue
# 如果栈顶字符大于当前字符，且后面还会出现
while stack and c < stack[-1] and i < last_occurrence[stack[-1]]:
seen.remove(stack.pop())
stack.append(c)
seen.add(c)
return ''.join(stack)
# 示例
# 输入: "bcabc"
# 输出: "abc"关键技巧：
记录每个字符最后出现的位置
维护单调递增栈
使用集合记录栈中已有字符
9. 768. 最多能完成排序的块 II ⭐⭐⭐
题目：将数组分成最多的块，对每个块单独排序后，连接起来的结果与原数组排序后的结果相同
def maxChunksToSorted(arr):
stack = [] # 每个块的最大值
for num in arr:
if not stack or num >= stack[-1]:
stack.append(num)
else:
# 合并块
max_val = stack.pop()
while stack and num < stack[-1]:
stack.pop()
stack.append(max_val)
return len(stack)
# 示例
# 输入: arr = [2,1,3,4,4]
# 输出: 4思路：
栈中存储每个块的最大值
遇到更小的数字时，需要合并前面的块
五、解题技巧总结
总结表格
关键区分：
如果当前元素是参考点（如波峰浪谷的j），要找比它小的 → 递增栈
如果当前元素是被比较点（如每日温度的今天），要找比它大的 → 递减栈
模板选择
# 通用模板
def monotonic_stack_template(arr, mode='greater'):
stack = []
result = [-1] * len(arr)
for i, val in enumerate(arr):
if mode == 'greater':
# 找下一个更大元素
while stack and arr[stack[-1]] < val:
idx = stack.pop()
result[idx] = i # 或 val
else:
# 找下一个更小元素
while stack and arr[stack[-1]] > val:
idx = stack.pop()
result[idx] = i # 或 val
stack.append(i)
return result特殊处理技巧
技巧1：添加哨兵元素
# 在84题中，添加高度0确保所有柱子被处理
heights.append(0)技巧2：存储额外信息
# 在901题中，存储(价格, 跨度)对
stack.append((price, span))技巧3：处理循环数组
# 在503题中，遍历2n次
for i in range(2 * n):
idx = i % n
# ... 处理逻辑六、练习建议
刷题顺序建议：
基础：496 → 739 → 901
进阶：84 → 42
变形：85 → 402 → 316
综合：768 → 1081（与316类似）
重点掌握：
84题（柱状图最大矩形）- 面试高频
42题（接雨水）- 多种解法对比
739题（每日温度）- 经典入门