🧱 01-数据结构与算法 · 主题 4:栈与队列(含单调栈)¶
栈解决「最近匹配/嵌套」类问题,单调栈把「下一个更大/更小元素」从 $O(n^2)$ 降到 $O(n)$。 本 notebook 目标:吃透栈队列基本功 → 掌握单调栈/单调队列模板 → 吃透 7 道高频题 → 通过 25 道自测。
前置:主题 1-3。运行环境:Python 3.8+,无第三方依赖。
核心概念¶
(a) 🗂️ 栈与队列:基本功、单调栈与单调队列模板¶
栈解决"最近匹配/嵌套"类问题,单调栈把"下一个更大/更小元素"从 O(n²) 降到 O(n)。本 notebook 吃透栈队列基本功,掌握单调栈/单调队列模板,精讲 7 道高频题。
flowchart TB
N1["🧱 栈与队列心智模型"] --> N2["基本功三题:232 / 20 / 155"]
N1 --> N3["单调栈模板:739 每日温度"]
N3 --> N4["单调栈进阶:503 / 84 / 42"]
N1 --> N5["单调队列:239 滑动窗口最大值"]
N1 --> N6["栈模拟展开:394 字符串解码"]
N2 --> N7["复杂度总表"]
N4 --> N8["常见 bug 与边界"]
N5 --> N8
N8 --> N9["面试追问与自测"]
- N1 · 栈与队列心智模型:栈像一摞盘子后进先出(LIFO),队列像排队先进先出(FIFO),基本操作都是 O(1)。碰到"最近相关性"(括号、撤销、函数调用)优先想栈。
- N2 · 基本功三题:双栈实现队列(232)、有效括号匹配(20)、最小栈 155(辅助栈记录历史最小值)——把这三题写熟,栈的直觉就建立起来了。
- N3 · 单调栈模板:单调栈维护一个"单调递增/递减"的栈,用来找"下一个更大/更小元素":每日温度就是标准模板,每个元素最多进出栈一次,整体 O(n)。
- N4 · 单调栈进阶:循环数组绕两圈(503)、柱状图最大矩形用"左右第一个更矮"(84)、接雨水用"左右边界夹出水量"(42)——同一个栈的三种变形。
- N5 · 单调队列:双端队列维护窗口内的最值:滑动窗口最大值(239)让队头永远是窗口最大,过期元素从队头弹出,同样是均摊 O(n)。
- N6 · 栈模拟展开:字符串解码(394)用数字栈 + 字符串栈,碰到右括号就弹栈拼接——栈天然适合处理嵌套结构。
- N7 · 复杂度总表:一张表对比栈/队列/单调栈/单调队列的时间与空间,是面试 30 秒答题的素材,要能脱口而出。
- N8 · 常见 bug 与边界:栈为空时 peek/pop、单调栈忘弹过期元素、边界索引越界——每一条都有对应踩坑案例,写单调栈前先默写模板。
- N9 · 面试追问与自测:追问区讲清单调栈通用模板、能解决的问题家族(矩形/雨水/滑动窗口/DP 优化),最后用 L1/L2/L3 自测收尾。
§1 心智模型与复杂度¶
栈(LIFO)¶
像一摞盘子:后进先出。只操作栈顶:
- push / pop / peek(top)均为 $O(1)$
- 适用:括号匹配、递归转迭代、最近相关性问题(撤销、函数调用栈)
队列(FIFO)¶
像排队:先进先出。队首出、队尾进,均为 $O(1)$。
- 适用:BFS(主题 10)、滑动窗口
单调栈 / 单调队列(本主题重点)¶
栈内元素保持单调(递增或递减),每次弹出「被当前元素淘汰」的旧元素:
| 问题 | 单调方向 | 弹出条件 |
|---|---|---|
| 下一个更大元素 | 栈底到栈顶递减 | $a_{top} < a_i$ 时弹出 |
| 下一个更小元素 | 栈底到栈顶递增 | $a_{top} > a_i$ 时弹出 |
| 窗口最大值(单调队列) | 队首到队尾递减 | 队尾 $\le a_i$ 时弹出 |
复杂度:每个元素至多进栈一次、出栈一次 → 总 $O(n)$。
§2 用栈实现队列(LeetCode 232):双栈法¶
题目:只用两个栈实现队列的 push / pop / peek / empty。
思路:
in_stack负责入队(push 直接压入)out_stack负责出队:只有当 out 为空时,才把 in 全部倒进 out(此时顺序反转,栈顶即队首)
均摊复杂度推导:每个元素最多被「倒入」一次、「倒出」一次:
$$\text{pop 均摊成本} = \frac{\text{总搬移 } O(n) + n \times O(1)}{n} = O(1)$$
关键:倒置时机是「out 为空时」——不是每次 pop 都倒。
💡 对称题:用两个队列实现栈(225)——push 时把旧元素全部移到新元素后面(旋转),保证队首即栈顶。
# ---- matplotlib 中文字体(防图内中文乱码)----
import matplotlib
matplotlib.rcParams['font.sans-serif'] = ['Microsoft YaHei', 'SimHei', 'Songti SC', 'Arial Unicode MS', 'DejaVu Sans']
matplotlib.rcParams['axes.unicode_minus'] = False
# -------------------------------------------
# ════════════════════════════════════════════════════════════════════════
# 【单元目标】LeetCode 232 用栈实现队列:只借助两个栈实现先进先出(FIFO)语义,
# 四操作 push / pop / peek / empty,其中 pop / peek 均摊 O(1)。
# 【算法思路】双栈分工:in_st 负责入队(push 直接压入);out_st 负责出队;
# _transfer:仅当 out_st 为空时,把 in_st 全部弹出压入 out_st——两次「后进先出」叠加
# 抵消为「先进先出」,栈顶变成队首;均摊 O(1) 的关键是「倒置时机是 out 为空时」,
# 而非每次 pop 都倒(整体搬移 O(n) 摊到 n 次 pop 上)。
# 【变量含义】in_st=入队栈(队尾方向);out_st=出队栈(倒置后栈顶即队首);x=入队元素。
# 【循环不变量】out_st 非空时,其栈顶恒为当前队首(FIFO 顺序已倒置就绪);
# 入队元素若压在 in_st 中,一定比 out_st 中所有元素「更新」,绝不出现在队首。
# 【关键边界】_transfer 只在 not out_st 时执行(否则会打乱已就绪的出队顺序);
# empty() 必须同时检查两个栈(一个空不代表队列空);peek 复用 _transfer 但不 pop。
# 【复杂度】push O(1);pop / peek 均摊 O(1)(每个元素最多被搬移一次);空间 O(n)。
# ════════════════════════════════════════════════════════════════════════
# 232. 用栈实现队列:双栈法——in_st 负责入队,out_st 负责出队(倒置后栈顶即队首),均摊 O(1)
class MyQueue:
# 双栈实现队列:in_st 负责入队,out_st 负责出队(倒置后栈顶即队首)
def __init__(self):
self.in_st = [] # 入队栈
self.out_st = [] # 出队栈
def push(self, x):
self.in_st.append(x) # 入队:直接压入入队栈
def pop(self):
self._transfer() # 确保 out 栈里有元素再弹出
return self.out_st.pop() # 弹出栈顶即队首元素
def peek(self):
self._transfer()
return self.out_st[-1] # 查看队首(不弹出)
def empty(self):
return not self.in_st and not self.out_st # 两个栈都空才为空
def _transfer(self):
if not self.out_st: # 关键:仅当 out 为空时才倒置
while self.in_st:
self.out_st.append(self.in_st.pop()) # 把入队栈倒进出队栈,顺序反转
q = MyQueue()
q.push(1); q.push(2)
print('peek =', q.peek()) # 期望 1
print('pop =', q.pop()) # 期望 1
print('empty =', q.empty()) # 期望 False
q.push(3)
print('pop =', q.pop()) # 期望 2
print('pop =', q.pop()) # 期望 3
print('empty =', q.empty()) # 期望 True
peek = 1 pop = 1 empty = False pop = 2 pop = 3 empty = True
§3 有效括号(LeetCode 20)¶
题目:判断括号字符串是否有效(匹配、无交叉)。
思路:
- 左括号(
([{)→ 入栈 - 右括号 → 检查栈顶是否为对应左括号:不匹配/栈空 → False
- 结束 → 栈必须为空(否则有未闭合左括号)
为什么用栈:括号的「最近匹配」特性——最内层先闭合,正好对应后进先出。
复杂度:时间 $O(n)$,空间 $O(n)$(最坏全为左括号)。
💡 变体:最长有效括号(32,DP/栈)、删除无效的括号(301)、括号生成(22,回溯)。
✍️ §3.1 手算括号匹配:{[()]} 与 {[}] 的栈过程¶
遇到左括号入栈,遇到右括号检查栈顶是否匹配再弹出——两组括号手算,对比合法与非法。
设定 A:{[()]}
| 字符 | 动作 | 栈 |
|---|---|---|
{ |
入 | { |
[ |
入 | {[ |
( |
入 | {[( |
) |
栈顶 ( 匹配 → 弹 |
{[ |
] |
栈顶 [ 匹配 → 弹 |
{ |
} |
栈顶 { 匹配 → 弹 |
空 ✓ 合法 |
设定 B:{[}]
| 字符 | 动作 | 栈 |
|---|---|---|
| { | 入 | { |
| [ | 入 | {[ |
| } | 栈顶 [ ≠ } → 非法 ✗ |
手算收获:
- 栈天然匹配"最近的未闭合左括号"(LIFO)——字符串合法当且仅当"每步栈顶正确配对 + 最后栈空"
- 右括号时先判栈空再弹:
}]直接非法(栈空却要匹配)——§12 常见 bug"栈空判断" - 复杂度 $O(n)$:每个字符至多入栈/出栈一次;空间 $O(n)$ 最坏(全是左括号)
- 变体:最长的有效括号(32)用栈存下标,或"任意括号种类多"——套路不变
下面 numpy 复算。
# ---- §3.1 验证:numpy 复算括号匹配 ----
def is_valid(s):
st, m = [], {')': '(', ']': '[', '}': '{'}
for ch in s:
if ch in '([{':
st.append(ch)
elif not st or st.pop() != m[ch]:
return False
return not st
print(f'{{[()]}} → {is_valid("{[()]}")}')
print(f'{{[}} → {is_valid("{[}]")}')
assert is_valid('{[()]}') and not is_valid('{[}]')
print('\n✓ 与手算一致')
# ════════════════════════════════════════════════════════════════════════
# 【单元目标】LeetCode 20 有效的括号:判断字符串是否由正确匹配、无交叉的括号对组成。
# 【算法思路】利用栈的「后进先出」匹配括号的「最近闭合」特性:
# 左括号(( [ {)→ 入栈;右括号 → 检查栈顶是否为对应的左括号:
# 栈空(没有左括号可配)或栈顶不匹配 → 非法;匹配则弹出;
# 全部扫描结束后栈必须为空(否则有未闭合的左括号)。
# 【变量含义】s=输入括号字符串;stack=左括号栈;pairs=右括号→对应左括号的映射表;ch=当前字符。
# 【循环不变量】扫描到任意位置时,stack 中存的是「尚未闭合的左括号」,按后进先出顺序等待匹配;
# 栈内左括号的相对顺序与它们在 s 中的顺序一致(交叉嵌套必然破坏匹配)。
# 【关键边界】右括号必须先判 not stack(如 s=')' 开头,栈空直接 False,防止 stack[-1] 越界);
# 交叉嵌套 '([)]' 会在第二个右括号 ')' 时栈顶是 '[' 而失配(返回 False);
# 最后 return not stack(栈非空说明有左括号未闭合)。
# 【复杂度】时间 O(n)(一趟扫描,每次栈操作 O(1));空间 O(n)(最坏全是左括号,栈长 n)。
# ════════════════════════════════════════════════════════════════════════
# 20. 有效的括号:用栈匹配最近的一对,遇到右括号时检查栈顶是否是对应的左括号
def is_valid(s):
stack = []
pairs = {')': '(', ']': '[', '}': '{'}
for ch in s:
if ch in pairs: # 右括号:检查栈顶
if not stack or stack[-1] != pairs[ch]:
return False
stack.pop()
else: # 左括号:入栈
stack.append(ch)
return not stack
print(is_valid('()[]{}')) # 期望 True
print(is_valid('([)]')) # 期望 False(交叉嵌套)
print(is_valid('({[]})')) # 期望 True
print(is_valid('(')) # 期望 False
print(is_valid(')(')) # 期望 False
True False True False False
§4 最小栈(LeetCode 155)¶
题目:常数时间取栈中最小值。
思路:辅助栈 min_st 与主栈同步,min_st[i] 恒为「前 i+1 个元素的最小值」:
$$\text{min\_st}[i] = \min(\text{st}[i],\ \text{min\_st}[i-1])$$
push 时压入 $\min(val, \text{当前最小})$,pop 时同步弹出。
复杂度:四种操作均 $O(1)$,空间 $O(n)$。
💡 空间优化版:min_st 只在出现新的更小值时才压入(值不重复时省空间);或单栈存差值。
# ════════════════════════════════════════════════════════════════════════
# 【单元目标】LeetCode 155 最小栈:在支持 push / pop / top 的基础上,get_min 也要 O(1)。
# 【算法思路】主栈 st + 辅助栈 min_st 同步压弹:min_st[i] 恒为「前 i+1 个元素的最小值」,
# 递推式 min_st[i] = min(st[i], min_st[i-1]);实现上 push 时若 val 更小则压入 val,
# 否则压入当前最小值(复制栈顶),保证两栈等长、pop 可同步弹出。
# 【变量含义】st=主栈(存真实元素);min_st=辅助栈(栈顶即当前最小值);val=新压入的值。
# 【循环不变量】任意时刻两栈长度相等;min_st 的栈顶恒等于 st 中所有元素的最小值;
# pop 后 min_st 栈顶自动变为「除去该元素后」的最小值(无需重新计算)。
# 【关键边界】push 时比较用 val <= min_st[-1](相等值也要压入,否则 pop 掉唯一最小值时信息丢失);
# 空栈调用 pop / top / get_min 由题目保证不发生;pop 必须两栈同步。
# 【复杂度】四种操作均 O(1);空间 O(n)(辅助栈与主栈等长,可优化为只在更小值时入栈)。
# ════════════════════════════════════════════════════════════════════════
# 155. 最小栈:主栈 + 辅助栈同步维护「当前最小值」,get_min 直接返回辅助栈栈顶
class MinStack:
# 155. 最小栈:主栈 + 辅助栈同步维护「当前最小值」
def __init__(self):
self.st = [] # 主栈
self.min_st = [] # 辅助栈:min_st[i] = 前 i+1 个元素的最小值
def push(self, val):
self.st.append(val)
if not self.min_st or val <= self.min_st[-1]:
self.min_st.append(val) # 出现更小值才入辅助栈
else:
self.min_st.append(self.min_st[-1]) # 否则复制当前最小值
def pop(self):
self.st.pop() # 主栈弹出
self.min_st.pop() # 辅助栈同步弹出
def top(self):
return self.st[-1] # 栈顶元素
def get_min(self):
return self.min_st[-1] # 辅助栈栈顶即当前最小值
ms = MinStack()
ms.push(-2); ms.push(0); ms.push(-3)
print('min =', ms.get_min()) # 期望 -3
ms.pop()
print('top =', ms.top()) # 期望 0
print('min =', ms.get_min()) # 期望 -2
ms.push(-5)
print('min =', ms.get_min()) # 期望 -5
min = -3 top = 0 min = -2 min = -5
§5 单调栈:每日温度(LeetCode 739)¶
题目:每个位置右边第一个更高温度的距离。
问题抽象(下一个更大元素):
$$nxt[i] = j, \quad j = \min\{ j > i : a_j > a_i \}$$
单调递减栈(栈内存下标,栈底到栈顶值递减):
- 新元素 $a_i$ 比栈顶 $a_{top}$ 大 → 弹出栈顶,它的下一个更大元素就是 $a_i$(距离 $i - top$)
- 新元素 $\le$ 栈顶 → 入栈(保持递减)
正确性:栈内元素的下一个更大元素一定在栈外右侧第一个更大的新元素处结算——栈保证了「还没找到答案的」元素按递减排列,一旦来了更大的就集体结算。
复杂度:时间 $O(n)$(每元素进出栈各一次),空间 $O(n)$。
# ════════════════════════════════════════════════════════════════════════
# 【单元目标】LeetCode 739 每日温度:求每个位置右边第一个更高温度的「距离天数」,
# 本质是「下一个更大元素」问题(比较的是值、记录的是距离)。
# 【算法思路】单调递减栈存下标(栈底到栈顶对应的温度递减):
# 扫描到温度 t 时,while 栈顶温度 < t:弹出栈顶 j,它的下一个更大元素就是当前 i,
# 答案 res[j] = i - j(距离);否则把 i 入栈。栈内永远只留「还没找到答案」的递减序列,
# 一旦出现更大的温度就集体结算——每个元素进出栈各一次 ⇒ O(n)。
# 【变量含义】temps=温度数组;n=长度;res=答案数组(初始全 0,找不到更大保持 0);
# stack=存下标的单调递减栈;i=当前下标;t=当前温度;j=被弹出的栈顶下标。
# 【循环不变量】任意时刻,栈内下标对应的温度从栈底到栈顶严格递减,且都是「等待更大温度结算」的元素;
# res 中已结算的位置都填上了正确的距离。
# 【关键边界】弹出条件是 temps[stack[-1]] < t(相等不结算:要严格更高,用 < 而非 <=);
# 降序数组(如 [90,80,70])全程无人可结算,res 全 0;
# 下标入栈而非温度入栈(结算需要距离 i - j)。
# 【复杂度】时间 O(n)(每个下标最多入栈一次、弹出一次);空间 O(n)(栈 + 结果数组)。
# ════════════════════════════════════════════════════════════════════════
# 739. 每日温度:单调递减栈存下标,遇到更高温度时结算栈内所有「等待中的」天数
def daily_temperatures(temps):
n = len(temps)
res = [0] * n
stack = [] # 存下标,栈底到栈顶值递减
for i, t in enumerate(temps):
while stack and temps[stack[-1]] < t:
j = stack.pop()
res[j] = i - j # j 的下一个更大元素在 i
stack.append(i)
return res
print('test1:', daily_temperatures([73, 74, 75, 71, 69, 72, 76, 73]))
print(' 期望 [1, 1, 4, 2, 1, 1, 0, 0]')
print('test2:', daily_temperatures([30, 40, 50, 60])) # 期望 [1,1,1,0]
print('test3:', daily_temperatures([30, 60, 90])) # 期望 [1,1,0]
print('test4:', daily_temperatures([90, 80, 70])) # 期望 [0,0,0](降序,无更大)
test1: [1, 1, 4, 2, 1, 1, 0, 0]
期望 [1, 1, 4, 2, 1, 1, 0, 0]
test2: [1, 1, 1, 0]
test3: [1, 1, 0]
test4: [0, 0, 0]
§6 下一个更大元素 II(LeetCode 503):循环数组¶
题目:给定循环数组(末尾接回开头),求每个元素右边第一个更大的值,没有则为 -1。
与 739 的区别:数组首尾相连,所以「右边」可以绕一圈。
循环数组技巧:遍历 $2n$ 次,用下标 $i \bmod n$ 取真实元素——相当于把数组复制两份拼在一起看。
单调递减栈 + 只在第一轮入栈:
- 栈内存下标(值递减),弹出时结算「下一个更大元素」
- 第二轮遍历不再入栈(下标会重复),只用于让第一轮剩下的元素有机会被绕回的值结算
复杂度:时间 $O(n)$,空间 $O(n)$。
# ════════════════════════════════════════════════════════════════════════
# 【单元目标】LeetCode 503 下一个更大元素 II:在「循环数组」(末尾接回开头)上求每个元素的
# 右边第一个更大值,找不到则填 -1——比 739 多一个「绕一圈」的维度。
# 【算法思路】循环数组技巧:遍历 2n 个位置(k 取 0..2n-1),用 i = k % n 访问真实元素,
# 等价于把数组复制两份拼接后看。单调递减栈存下标:
# 遇到比栈顶更大的值时弹出结算(res[弹出下标] = 当前值);
# 关键:只在第一轮(k < n)把下标入栈,第二轮只负责结算——否则重复入栈会让
# 同一个下标被结算两次或无限循环。
# 【变量含义】nums=循环数组;n=长度;res=结果数组(初始全 -1);stack=单调递减栈(存下标);
# k=遍历轮次计数(0..2n-1);i=k % n 的真实下标。
# 【循环不变量】任意时刻栈内下标对应值递减,且都是「尚未找到下一个更大元素」的候选;
# 每个下标最多入栈一次(第一轮)、出栈结算一次。
# 【关键边界】入栈限制 if k < n(第二轮 k >= n 只结算不入栈);
# 最大值(或全局递减)找不到更大的元素,保持 -1;空数组返回 []。
# 结算条件是 nums[stack[-1]] < nums[i](严格更大)。
# 【复杂度】时间 O(n)(2n 次迭代,每下标进出栈一次);空间 O(n)(栈 + 结果数组)。
# ════════════════════════════════════════════════════════════════════════
# 503. 下一个更大元素 II:循环数组绕两圈(i 取 0..2n-1,用 i%n 访问),单调栈求解
def next_greater_element_ii(nums):
n = len(nums)
res = [-1] * n
stack = [] # 单调递减栈,存下标
for k in range(2 * n):
i = k % n # 循环数组:下标绕回
while stack and nums[stack[-1]] < nums[i]:
res[stack.pop()] = nums[i] # 栈顶的下一个更大元素就是 nums[i]
if k < n: # 只在第一轮入栈,第二轮只结算不入栈
stack.append(i)
return res
assert next_greater_element_ii([1, 2, 1]) == [2, -1, 2]
assert next_greater_element_ii([1, 2, 3, 4, 3]) == [2, 3, 4, -1, 4]
assert next_greater_element_ii([5, 4, 3, 2, 1]) == [-1, 5, 5, 5, 5] # 降序:除最大值外,绕一圈都被 5 兜底
assert next_greater_element_ii([]) == []
print('503 next_greater_element_ii OK')
503 next_greater_element_ii OK
§7 柱状图中最大的矩形(LeetCode 84):单调栈进阶¶
题目:直方图中最大矩形面积。
核心公式:对每根柱子 $i$,找它左右第一个更矮的柱子 $L_i$、$R_i$:
$$\text{area}(i) = h_i \times (R_i - L_i - 1)$$
最大面积 = 所有柱子作为「矩形高度」时的最大值:
$$\text{best} = \max_i \, h_i \cdot (R_i - L_i - 1)$$
单调栈做法:维护递增栈。弹出时(遇到更矮柱子 $h_i$),被弹出的 $h_{idx}$ 的右边界就是 $i$,左边界就是栈内下一个元素——两个边界同时确定。
哨兵技巧:末尾补一个高度 0,强制清空栈结算所有柱子。
复杂度:时间 $O(n)$,空间 $O(n)$。
# ════════════════════════════════════════════════════════════════════════
# 【单元目标】LeetCode 84 柱状图中最大的矩形:求直方图中能画出的最大矩形面积(单调栈进阶题)。
# 【算法思路】核心公式:以柱子 i 为高的最大矩形宽 = R_i - L_i - 1,其中 L_i / R_i 是 i 左右
# 第一个更矮的柱子(越界视为 -1 / n),面积 = h_i × (R_i - L_i - 1),对每根柱子取 max。
# 单调递增栈:遇到更矮的柱子 h 时,被弹出的 idx 的右边界就是当前 i、左边界就是弹出后
# 的新栈顶(或 -1)——左右边界在弹出时同时确定,因此能一次扫描算完全部柱子。
# 末尾追加哨兵高度 0,强制弹出栈内剩余所有柱子完成结算。
# 【变量含义】heights=柱高数组(原地追加 [0] 作哨兵);stack=单调递增栈(存下标);
# best=当前最大面积;i=当前下标;h=当前高度;idx=被弹出的栈顶下标;
# left=弹出后新栈顶(左边界,栈空取 -1)。
# 【循环不变量】栈内下标对应高度严格递增;每个下标入栈一次、弹出结算一次;
# best 恒为已处理部分中能取到的最大矩形面积。
# 【关键边界】弹出条件 heights[stack[-1]] > h(严格更高才弹,相等不弹——相等高度延后结算能覆盖更宽);
# 宽度计算 i - left - 1 用的是「左右第一个更矮」的夹距;
# 哨兵 0 保证栈内最后剩余的元素(一路递增的柱子)也能被结算。
# 【复杂度】时间 O(n)(每下标进出栈各一次);空间 O(n)(栈,不含结果数组)。
# ════════════════════════════════════════════════════════════════════════
# 84. 柱状图中最大的矩形:单调栈找每个柱子的「左右第一个更矮」位置,哨兵 0 强制结算所有面积
def largest_rectangle_area(heights):
heights = heights + [0] # 哨兵:最后强制弹出所有元素结算
stack = []
best = 0
for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
idx = stack.pop()
left = stack[-1] if stack else -1
best = max(best, heights[idx] * (i - left - 1))
stack.append(i)
return best
print('test1:', largest_rectangle_area([2, 1, 5, 6, 2, 3])) # 期望 10
print('test2:', largest_rectangle_area([2, 4])) # 期望 4
print('test3:', largest_rectangle_area([1])) # 期望 1
print('test4:', largest_rectangle_area([6, 5, 4])) # 期望 12(高度 4 宽 3)
test1: 10 test2: 4 test3: 1 test4: 12
§8 接雨水(LeetCode 42):单调栈版¶
题目:每个位置能接多少雨水(与 02 主题 §3 双指针版同一题,换一种解法)。
单调递减栈(存下标):当前柱子 $h_i$ 高于栈顶时,弹出栈顶 $top$:
- $top$ 就是凹槽底,它左右两边的「墙」分别是新栈顶 $left$ 与当前 $i$
- 凹槽水深:$h = \min(h_{left},\ h_i) - h_{top}$(短板决定,可能为 0)
- 凹槽宽度:$w = i - left - 1$
$$\text{total} += w \times h$$
复杂度:时间 $O(n)$(每元素进出栈各一次),空间 $O(n)$。
# ════════════════════════════════════════════════════════════════════════
# 【单元目标】LeetCode 42 接雨水(单调栈版):统计每个位置能接的雨水总量——
# 与 02 主题的双指针版同一道题,这里换单调栈视角,方便对照两种解法。
# 【算法思路】单调递减栈存下标。扫描到高度 height[i] 高于栈顶时,弹出栈顶 top:
# top 就是「凹槽底」,它左右两边的墙分别是弹出后的新栈顶 left 与当前 i;
# 凹槽水深 h = min(height[left], height[i]) - height[top](短板决定,可能为 0);
# 凹槽宽度 w = i - left - 1;total += w × h。
# 相当于自底向上逐层结算每一处能存水的「盆地」。
# 【变量含义】height=柱高数组;n=长度;stack=单调递减栈(存下标);total=累计雨水量;
# i=当前下标;top=被弹出的凹槽底下标;left=凹槽左墙下标;h=水深;w=水宽。
# 【循环不变量】栈内下标对应高度递减;每个下标入栈一次、弹出结算一次;
# total 恒为已结算凹槽的正确水量之和。
# 【关键边界】弹出条件 height[stack[-1]] < height[i](当前更高才构成「坑」的右墙);
# 弹出后若栈空(left 不存在)则左侧没有墙,存不住水,break 跳过本次结算;
# 单调数组(如 [1,2,3])没有凹槽,水量为 0;空数组返回 0。
# 【复杂度】时间 O(n)(每下标进出栈各一次);空间 O(n)(栈)。
# ════════════════════════════════════════════════════════════════════════
# 42. 接雨水(单调栈版):维护递减栈,出现「坑」(栈顶比当前矮)时结算左右边界之间的水量
def trap_stack(height):
n = len(height)
stack = [] # 单调递减栈,存下标
total = 0
for i in range(n):
while stack and height[stack[-1]] < height[i]:
top = stack.pop() # 凹槽底
if not stack: # 左边没有墙,存不住水
break
left = stack[-1] # 凹槽左墙
h = min(height[left], height[i]) - height[top]
w = i - left - 1
total += w * h
stack.append(i)
return total
assert trap_stack([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]) == 6
assert trap_stack([4, 2, 0, 3, 2, 5]) == 9
assert trap_stack([1, 2, 3]) == 0
assert trap_stack([]) == 0
print('42 trap_stack OK')
42 trap_stack OK
§9 滑动窗口最大值(LeetCode 239):单调队列¶
题目:每个长度为 $k$ 的窗口内最大值。
窗口最大值公式:
$$w_i = \max\{ a_{i-k+1},\, a_{i-k+2},\, \dots,\, a_i \}$$
单调队列(双端队列,队首到队尾值递减):
- 淘汰过期:队首下标 $\le i - k$ 时出队
- 淘汰更小:队尾值 $\le a_i$ 时出队(它们不可能再成为最大值)
- 入队 $i$,窗口成形后队首即最大值
为什么对:队列中下标递增、值递减;任何「被更小值挡住的更大值」已被淘汰,队首就是当前窗口最大值。
复杂度:时间 $O(n)$(每元素进出队各一次),空间 $O(k)$。
# ════════════════════════════════════════════════════════════════════════
# 【单元目标】LeetCode 239 滑动窗口最大值:求每个长度为 k 的连续窗口内的最大值,
# 用「单调队列」(双端队列)把暴力 O(n·k) 降到 O(n)。
# 【算法思路】双端队列 dq 存下标,且对应值从队首到队尾严格递减;每轮三步:
# ① 淘汰过期:队首下标 <= i-k 说明已滑出窗口,popleft;
# ② 淘汰更小:队尾值 <= 当前值 x 的全部 pop(它们之后不可能再成为窗口最大值);
# ③ 入队 i;当窗口成形(i >= k-1)后,队首即当前窗口最大值。
# 【变量含义】nums=输入数组;k=窗口长度;dq=存下标的双端队列(值递减);res=结果数组;
# i=当前右端下标;x=当前值。
# 【循环不变量】任意时刻 dq 中下标递增、对应值严格递减,且下标全部落在当前窗口 [i-k+1, i] 内;
# 队首恒为窗口最大值(任何比它靠后且更大的值都已淘汰它之前的更小者)。
# 【关键边界】淘汰相等值用 <=(相等时更靠后的下标寿命更长,应留后者)——与每日温度的 < 形成对比;
# 过期判断 dq[0] <= i - k(下标从 0 开始);窗口未满(i < k-1)时不输出;
# k=1 时每个元素自身即窗口最大值,队列恒为单元素。
# 【复杂度】时间 O(n)(每个下标最多入队一次、出队一次);空间 O(k)(队列最多存 k 个下标)。
# ════════════════════════════════════════════════════════════════════════
# 239. 滑动窗口最大值:单调队列存下标且值递减,队头永远是窗口最大值,过期元素从队头弹出
from collections import deque
def max_sliding_window(nums, k):
dq = deque() # 存下标,值递减
res = []
for i, x in enumerate(nums):
# 1. 队首过期
if dq and dq[0] <= i - k:
dq.popleft()
# 2. 淘汰队尾所有更小/相等值
while dq and nums[dq[-1]] <= x:
dq.pop()
dq.append(i)
# 3. 窗口成形后取队首
if i >= k - 1:
res.append(nums[dq[0]])
return res
print('test1:', max_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3)) # [3,3,5,5,6,7]
print('test2:', max_sliding_window([1], 1)) # [1]
print('test3:', max_sliding_window([7, 2, 4], 2)) # [7,4]
print('test4:', max_sliding_window([9, 8, 7, 6], 3)) # [9,8](递减,无淘汰)
test1: [3, 3, 5, 5, 6, 7] test2: [1] test3: [7, 4] test4: [9, 8]
单调队列在 DP 中的应用¶
💡 滑动窗口型 DP(如带窗口约束的序列问题)可用单调队列把状态转移从 $O(k)$ 压到 $O(1)$。
队列里只存「当前窗口内单调有序、可能成为最优」的候选下标,队头过期就弹出、队尾被更优者淘汰——每个候选进出队列各一次。
典型题:跳跃游戏 VI(LeetCode 1696)、带窗口约束的最长上升子序列类问题。
§10 字符串解码(LeetCode 394):栈模拟展开¶
题目:3[a2[c]] → accaccacc。
思路:一个栈存「遇 [ 时的现场」:
$$\text{stack 元素} = (\text{前缀字符串},\ \text{重复次数})$$
- 数字:累积
num = num*10 + d(处理多位数) [:把(cur, num)压栈,重置 cur / num]:弹出(prev, k),cur = prev + cur * k- 字母:直接追加到 cur
复杂度:时间 $O(n \cdot k)$(k 为最大展开倍数,取决于输出规模),空间 $O(n)$(栈)。
💡 嵌套展开是栈的典型场景:内层先闭合(LIFO),与括号匹配同理。
# ════════════════════════════════════════════════════════════════════════
# 【单元目标】LeetCode 394 字符串解码:把编码串如 3[a2[c]] 展开为 accaccacc——
# 栈模拟「嵌套展开」的典型题,内层先闭合对应 LIFO 特性。
# 【算法思路】一个栈存「遇到 [ 时的现场」(前缀字符串, 重复次数);线性扫描四种字符:
# 数字 → 累积 num = num*10 + d(处理多位数);
# [ → 把 (cur, num) 压栈存档,重置 cur=''、num=0 开始处理新一层;
# ] → 弹出 (prev, k),cur = prev + cur * k(把本层展开结果拼回前缀);
# 字母 → 直接追加到 cur。
# 【变量含义】s=编码字符串;stack=现场栈(元素为 (前缀, 次数));cur=当前层已解析字符串;
# num=当前层累积的重复次数;ch=当前字符;prev=外层前缀;k=本层重复次数。
# 【循环不变量】扫描到任意位置时,cur 是「当前层(最近一个未闭合 [ 之内)」已解析的内容;
# stack 从底到顶对应从外到内的各层现场,弹栈即按 LIFO 从内向外展开。
# 【关键边界】数字必须 num = num*10 + int(ch) 累积('100[le]' 是多位数用例);
# [ 时先存档再重置;] 时 cur * k 是 Python 字符串乘法(重复 k 遍);
# 嵌套时内层展开结果作为外层 cur 的一部分参与外层乘法——天然处理任意层嵌套。
# 【复杂度】时间 O(输出长度)(字符串乘法成本正比于展开结果,最坏 O(n·k));空间 O(n)(栈 + 当前串)。
# ════════════════════════════════════════════════════════════════════════
# 394. 字符串解码:数字栈 + 字符串栈,遇到右括号就弹栈拼接展开,天然处理嵌套结构
def decode_string(s):
stack = []
cur = ''
num = 0
for ch in s:
if ch.isdigit():
num = num * 10 + int(ch)
elif ch == '[':
stack.append((cur, num)) # 保存现场
cur = ''
num = 0
elif ch == ']':
prev, k = stack.pop()
cur = prev + cur * k
else:
cur += ch
return cur
print('test1:', decode_string('3[a]2[bc]')) # 期望 aaabcbc
print('test2:', decode_string('3[a2[c]]')) # 期望 accaccacc
print('test3:', decode_string('2[abc]3[cd]ef')) # 期望 abcabccdcdcdef
print('test4:', decode_string('abc3[cd]xyz')) # 期望 abccdcdcdxyz
print('test5:', decode_string('100[le]')) # 期望 le 重复 100 次(长度 200)
test1: aaabcbc test2: accaccacc test3: abcabccdcdcdef test4: abccdcdcdxyz test5: lelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelelele
§11 复杂度总表(背熟)¶
| 题 | 时间 | 空间 | 核心技巧 |
|---|---|---|---|
| 用栈实现队列 232 | 均摊 $O(1)$ | $O(n)$ | 双栈 + 空才倒 |
| 有效括号 20 | $O(n)$ | $O(n)$ | 栈匹配 |
| 最小栈 155 | $O(1)$ | $O(n)$ | 辅助栈 |
| 每日温度 739 | $O(n)$ | $O(n)$ | 单调递减栈 |
| 柱状图最大矩形 84 | $O(n)$ | $O(n)$ | 单调递增栈 + 哨兵 |
| 滑动窗口最大值 239 | $O(n)$ | $O(k)$ | 单调队列 |
| 字符串解码 394 | $O(nk)$ | $O(n)$ | 栈存现场 |
| 下一个更大元素 II 503 | $O(n)$ | $O(n)$ | 单调递减栈 + 两轮循环 |
| 接雨水 42(单调栈版) | $O(n)$ | $O(n)$ | 弹出时结算凹槽 |
一句话记忆¶
- 单调栈 / 队列 = 每个元素进出一次 → 为什么是 $O(n)$
- 栈解决「最近」问题,队列解决「窗口」问题,单调性消除「不可能成为答案」的候选
§12 常见 bug 与边界(面试踩坑区)¶
- 栈空判断:弹出前必须判
not stack(右括号开头 / 提前闭合) - 单调栈方向写反:下一个更大用递减栈(弹出更小的),下一个更小用递增栈——先用例子确认
- 哨兵缺失:84 题不加末尾 0 会漏结算栈内剩余元素
<=还是<:滑动窗口最大值用<=淘汰相等值(相等值更靠后更有利);每日温度用<(相等不结算)- 多位数:394 题数字要
num = num*10 + d,不是单个字符 - 双端队列队首过期判断:
dq[0] <= i - k,下标从 0 开始,别写成i-k+1 - 用 list 当队列:
pop(0)是 $O(n)$,必须用collections.deque
§13 面试追问与扩展(加分项)¶
13.1 单调栈的通用模板¶
stack = []
for i, x in enumerate(a):
while stack and 需要弹出(stack, x):
top = stack.pop()
结算答案(top, i) # 右边界就是 i
stack.append(i)
「需要弹出」与「结算」按题目定制;左边界 = 弹出后的新栈顶。
13.2 单调栈能解决的问题家族¶
- 下一个更大/更小元素(739、496、503)
- 两侧第一个更矮/更高 → 面积类(84、85 最大矩形)
- 去除使字典序最小(316 去除重复字母、402 移掉 K 位数字)
- 接雨水(42)的单调栈解法
13.3 手撕题¶
- 用两个栈实现队列 / 两个队列实现栈(互相考)
- 实现一个支持 min 的栈
- 表达式求值(逆波兰 150、基本计算器 227)
§14 自测清单(L1 必会 / L2 进阶 / L3 挑战)¶
L1 必会(10 题)¶
- 1. 有效的括号(LeetCode 20)
- 2. 最小栈(155)
- 3. 用栈实现队列(232)
- 4. 用队列实现栈(225)
- 5. 逆波兰表达式求值(150)
- 6. 删除字符串中的所有相邻重复项(1047)
- 7. 比较含退格的字符串(844)
- 8. 下一个更大元素 I(496)
- 9. 化栈为队列(面试手撕)
- 10. 每日温度(739)
L2 进阶(10 题)¶
- 11. 滑动窗口最大值(239)
- 12. 字符串解码(394)
- 13. 柱状图中最大的矩形(84)
- 14. 接雨水(42,单调栈版)
- 15. 移掉 K 位数字(402)
- 16. 去除重复字母(316)
- 17. 基本计算器 II(227)
- 18. 最长有效括号(32)
- 19. 最大矩形(85)
- 20. 下一个更大元素 II(503)
L3 挑战(5 题)¶
- 21. 132 模式(456)
- 22. 最大频率栈(895)
- 23. 原子的数量(726)
- 24. 子数组最小乘积的最大值(1856)
- 25. 统计全 1 子矩形(1504)
自测要点¶
- 5 分钟内盲写:有效括号、每日温度、滑动窗口最大值
- 讲清「单调栈为什么 O(n)」「为什么用 <= 淘汰相等值」
- 能画出 84 题的边界确定过程(弹出时左右边界同时确定)