📑 本页目录(点开跳转)
03 · 栈、队列和窗口:谁应该先出来
⏱ 10 分钟 | 两个栈实现队列、min 栈、滑动窗口最大值
🎯 一句话
这类题先不写代码,先问:我需要最早的、最新的,还是目前最大的那个?
三张处理单按 A、B、C 的顺序到达。排队办事先拿 A。桌上只能从顶上取纸,先拿 C。上一章逐层访问树节点时用的是前一种规则,本章把取出顺序单独拆开。
从同一端放入、取出。后进先出(Last In, First Out,LIFO)。A、B、C 依次压栈,弹出顺序为 C → B → A。
从队尾加入,从队首取出。先进先出(First In, First Out,FIFO)。A、B、C 依次入队,出队顺序为 A → B → C。
双端队列(double-ended queue,deque)允许在两端加入或取出元素,题 3 会用到。具体从哪端操作由算法决定。第 04 章的堆会按优先级取出元素,使用的是另一条规则。
🧩 题 1:用两个栈实现队列
一个栈负责“新来的放进去”,另一个负责“最早来的拿出来”。只有输出栈空了,才把输入栈整批倒过去。
手里只有两摞只能从顶上取的纸。把输入栈逐张搬到输出栈,原本压在最底下的 A 最后被搬过去,正好落在输出栈顶。
| 操作 | 输入栈 | 输出栈 | 取出 |
|---|---|---|---|
| 依次入队 A、B、C | A、B、C | 空 | — |
| 倒栈后首次出队 | 空 | C、B | A |
| 入队 D | D | C、B | — |
| 直接出队 | D | C | B |
| 直接出队 | D | 空 | C |
| 再倒栈并出队 | 空 | 空 | D |
若在输出栈还有 B 时把 D 倒上去,D 会抢到 B 前面。代码里的 if not self.outbox 就是倒栈的开关。两栈都空时,pop() 抛出 IndexError。本页三个 Python 示例都用 assert 核对结果,运行成功时无输出。
class TwoStackQueue:
def __init__(self):
self.inbox, self.outbox = [], []
def push(self, value):
self.inbox.append(value)
def pop(self):
if not self.outbox:
while self.inbox:
self.outbox.append(self.inbox.pop())
if not self.outbox:
raise IndexError("queue is empty")
return self.outbox.pop()
queue = TwoStackQueue()
for value in [1, 2, 3]:
queue.push(value)
assert [queue.pop(), queue.pop(), queue.pop()] == [1, 2, 3]
不变量。outbox 非空时,它的顶部是当前最早进入、还没出去的元素。输出栈空时,若输入栈里仍有元素,最早来的那个在输入栈底部。
把搬运次数记在每张单上。一次出队可能要搬完手上的 n 张单,最坏时间是 O(n)。但一张单在整个过程中至多经过四次栈顶操作。入输入栈一次,搬运时弹出和压入各一次,最后从输出栈弹出一次。
例如先入队 A、B、C,再连续出队三次。首次出队含 3 × 2 次搬运操作和 1 次最终弹出,其余两次只弹出。总操作数是 3 + 7 + 1 + 1 = 12,六次调用平均每次两次栈顶操作。把总成本分到所有调用上,就是摊还(amortized)分析。按栈顶操作计数,平均到每次调用为 O(1),即使某一次出队更慢。两个栈合计保存与待处理数成正比的元素,空间 O(n),这里 n 是队列当前元素数。
🧩 题 2:包含 min 函数的栈
别在每次 min() 时把栈扫一遍。再放一个 mins 栈:每一层都记“走到这里为止的最小值”。
栈里先放 5,再放两张都写着 2 的单。如果只记一个全局最小值,弹出顶上的 2 时,还要确认另一张 2 有没有留在栈里。最小值栈(min stack)在每次压栈时多存一份截至该层的最小值。弹出一层,下一层的记录就自动露出来。
| 操作 | 原值 data | 最小值记录 mins |
|---|---|---|
| 压入 5 | 5 | 5 |
| 压入 2 | 5、2 | 5、2 |
| 再压入 2 | 5、2、2 | 5、2、2 |
| 弹出一个 2 | 5、2 | 5、2 |
| 再弹出一个 2 | 5 | 5 |
原栈为空时,新值就是最小值。已有元素时,把新值和上一层的最小值取较小者。表里的记录依次是 5、min(2, 5) = 2、min(2, 2) = 2。代码用 append() 同步入栈,用两次 pop() 同步弹出。get_min() 用 mins[-1] 读取栈顶,不移除元素。
class MinStack:
def __init__(self):
self.data, self.mins = [], []
def push(self, value):
self.data.append(value)
self.mins.append(value if not self.mins else min(value, self.mins[-1]))
def pop(self):
self.mins.pop()
return self.data.pop()
def get_min(self):
return self.mins[-1]
stack = MinStack()
for value in [3, 1, 2]:
stack.push(value)
assert stack.get_min() == 1
stack.pop()
stack.pop()
assert stack.get_min() == 3
边界与成本。本例接收可相互比较的数值。空栈调用 pop() 或 get_min() 都会抛出 IndexError。每次操作至多一次大小比较和固定次数的栈顶操作,按每次比较的成本固定来计,get_min() 为 O(1),使用 Python 列表实现的栈更新摊还 O(1)。若原栈有 n 个元素,辅助栈就有 n 条记录,额外空间 O(n)。
🧩 题 3:滑动窗口的最大值
窗口向右移动时,过期下标从队首丢掉;新值进来前,把小于或等于它的候选从队尾丢掉。队列里只留可能成为最大值的人。
屏幕每次只显示连续两张数值单。显示框从左往右每次挪一格,每一格都要报出框里的最大值。每次重看框内所有数当然可以,但相邻两格有重叠。已经离开显示框的数要删掉,框内被新数压过的候选也可以提前删。
设 nums 是数列,位置从 0 编号,right 是本轮刚读到的位置,整数 k 是完整窗口的宽度。完整窗口往左还有 k − 1 格,最左位置为 right − k + 1。下标小于这个位置就已过期,也就是小于或等于 right − k。例如 right = 2、k = 2 时,最左是 2 − 2 + 1 = 1,下标 0 已经过期。
从新值进入那刻起,往右滑的任何窗口只要还包含较旧的候选,也会包含新值。若新值至少一样大,旧值可以从候选队尾丢掉。相等时留下更新的那个,日后会更晚过期。这条队列按进入顺序保存下标,对应值从队首到队尾严格递减,叫单调队列(monotonic queue)。因此队首就是当前最大值的下标。
| 新位置(值) | 从两端丢掉什么 | 本轮候选 | 输出 |
|---|---|---|---|
| 0(6) | 无 | 0(6) | 窗口还没满 |
| 1(2) | 无 | 0(6)、1(2) | 6 |
| 2(2) | 0 从队首过期,1 从队尾被新 2 替换 | 2(2) | 2 |
| 3(5) | 2 从队尾被 5 压过 | 3(5) | 5 |
| 4(1) | 无 | 3(5)、4(1) | 5 |
代码先用 popleft() 清理过期位置,再用 pop() 淘汰队尾候选,最后用 append() 加入新下标。至少读到第 k 项才输出,对应 right >= k - 1。若把过期条件误写成 下标 < right - k,表里新位置 2 那一轮就会错保住 6。
from collections import deque
def max_sliding_window(nums, k):
queue, answer = deque(), [] # queue 存下标,值从大到小
for right, value in enumerate(nums):
while queue and queue[0] <= right - k:
queue.popleft()
while queue and nums[queue[-1]] <= value:
queue.pop()
queue.append(right)
if right >= k - 1:
answer.append(nums[queue[0]])
return answer
assert max_sliding_window([2, 3, 4, 2, 6, 2, 5, 1], 3) == [4, 4, 6, 6, 6, 5]
⭐ 队列存下标不是细节:这样才能知道队首是否已经离开窗口。
边界。宽度 k = 1 时每个数就是本窗口答案,k 等于数列长度时只输出一次全局最大值。空输入或 k 大于数列长度时没有完整窗口,函数返回空列表。宽度必须是正整数,本示例未对不合法的宽度做显式报错。
数进出次数。设数列有 n 项,且 1 ≤ k ≤ n。逐窗扫描要读 n − k + 1 个窗口,每个窗口看 k 项。上例是 (5 − 2 + 1) × 2 = 8 次读数。候选队列里每个下标只入队一次,最多离队一次,上例入队 5 次、离队 3 次。这两种计数各自用来判断增长趋势。双端操作是 O(1),合计时间 O(n)。队列最多留 k 个下标,额外空间 O(k),输出列表另计。
🔗 这一章连到哪里
| 去哪 | 为什么 |
|---|---|
| 不靠数据的 AI 05 · 状态空间与搜索框架 | ⭐ 「谁应该先出来」正是那一章的全部问题:BFS、DFS、迭代加深、一致代价、A* 共用一个骨架,差别只在待展开集合用什么容器 |
本节回顾
栈管“最近”,队列管“最早”,单调队列管“窗口里还可能赢的人”。
✅ 检查点
滑动窗口最大值为什么能丢掉比新值小的队尾元素?
👀 看答案
新值更靠右,留得更久。此后只要窗口还包含旧值,也会包含至少一样大的新值。丢掉旧候选不会改变之后窗口返回的最大值。
输出栈还剩 C、B,右端的 B 在栈顶。现在入队 D,下一次出队应该取谁?
👀 看出队顺序
取 B。D 先进输入栈。输出栈还有 B、C 等待处理,取完它们以后才搬 D。
最小值栈先压入 8,再压入 4、4、6。弹出 6 和一个 4 后,get_min() 是多少?
👀 看最小值记录
返回 4。辅助栈压满时是 8、4、4、4,弹出两层后还有 8、4。再弹出剩下的 4,最小值才回到 8。
输入 9、4、4、3,宽度为 2。读到第二个 4 时,要从哪端清除哪些下标?
👀 看窗口淘汰
此时 right = 2,窗口只含下标 1 和 2。从队首移除下标 0 的 9,它已过期。再从队尾移除下标 1 的旧 4,留下下标 2 的新 4,当前最大值是 4。
⚡ 走神救援
- 两栈队列:输入栈收新元素,输出栈只在空时整批倒。
- min 栈:每层同步保存当时最小值。
- 窗口:过期从左丢,弱者从右丢,队首就是答案。