🏠 总目录📚 本教程 03 · 栈、队列与窗口:谁应该先出来 ← →
📑 本页目录(点开跳转)

03 · 栈、队列和窗口:谁应该先出来

⏱ 10 分钟 | 两个栈实现队列、min 栈、滑动窗口最大值

🎯 一句话

这类题先不写代码,先问:我需要最早的、最新的,还是目前最大的那个?

三张处理单按 A、B、C 的顺序到达。排队办事先拿 A。桌上只能从顶上取纸,先拿 C。上一章逐层访问树节点时用的是前一种规则,本章把取出顺序单独拆开。

栈(stack)

从同一端放入、取出。后进先出(Last In, First Out,LIFO)。A、B、C 依次压栈,弹出顺序为 C → B → A。

队列(queue)

从队尾加入,从队首取出。先进先出(First In, First Out,FIFO)。A、B、C 依次入队,出队顺序为 A → B → C。

双端队列(double-ended queue,deque)允许在两端加入或取出元素,题 3 会用到。具体从哪端操作由算法决定。第 04 章的堆会按优先级取出元素,使用的是另一条规则。

🧩 题 1:用两个栈实现队列

一个栈负责“新来的放进去”,另一个负责“最早来的拿出来”。只有输出栈空了,才把输入栈整批倒过去。

手里只有两摞只能从顶上取的纸。把输入栈逐张搬到输出栈,原本压在最底下的 A 最后被搬过去,正好落在输出栈顶。

两栈都按从底到顶书写,右端是栈顶
操作输入栈输出栈取出
依次入队 A、B、CA、B、C空—
倒栈后首次出队空C、BA
入队 DDC、B—
直接出队DCB
直接出队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
压入 555
压入 25、25、2
再压入 25、2、25、2、2
弹出一个 25、25、2
再弹出一个 255

原栈为空时,新值就是最小值。已有元素时,把新值和上一层的最小值取较小者。表里的记录依次是 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)。因此队首就是当前最大值的下标。

输入 6、2、2、5、1,k = 2。候选按「下标(值)」书写,左端为队首
新位置(值)从两端丢掉什么本轮候选输出
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。


⚡ 走神救援

继续: 04 · 二分、排序与堆:怎样少看一半

打卡记录保存在你的浏览器里,首页能看到总进度