专题进阶 · 栈与队列进阶推荐总顺序 · 第 42 / 148 课

用下标同时处理过期与支配关系,在线求每个固定窗口的最大值。

先学会这些,再进入本课 队列 单调栈 滑动窗口
还有 3 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 栈与队列进阶

单调队列Monotonic Queue

用双端队列维护窗口极值;移除过期下标和被新值支配的候选。

建议 40 分钟 · 含手算、代码与三层练习

本课要建立的能力

用下标同时处理过期与支配关系,在线求每个固定窗口的最大值。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

数组 [1,3,−1,−3,5],窗口宽 3。每次窗口右移,能否不重新扫描三个元素?

02一步步得到方法

保留未来仍可能成为最大值的候选

双端队列存下标,对应值从队首到队尾递减。新值 x 到来时,队尾若不大于 x,就可以移除:x 更大或相等,而且更晚过期,被移除的值在之后的共同窗口里不可能胜出。

队首仍需检查是否过期。下标≤i−k 时已离开以 i 结尾的窗口;这和因数值被支配而从队尾删除是两种不同操作。保存值而不保存下标会让重复值过期难以判断。

为什么两层循环仍是线性

每个下标只入队一次,只能从队首或队尾被删除一次。因此所有 while 的总弹出次数不超过 n。这个摊还论证与单调栈相同,而不是每个窗口各花 k 次。

存下标才能同时维护值与有效期

滑动窗口的候选不仅比较数值,还要知道何时离开窗口。存下标可以检查过期,并在需要时读取原数组值;只存值会让重复元素的过期关系难以区分。

队尾弹出被新元素支配的候选,因为新元素更靠右、活得更久且不更差。队首弹出已经过期的候选。这是两种不同理由,不应写成一个含糊的删除规则。

03把一个小例子完全算清楚

[1,3,−1,−3,5],k=3,队列写为 下标:值。

步骤计算与状态为什么这样做
i=0、1[0:1] → [1:3]3 支配更早的 1
i=2[1:3,2:−1],输出 3首个完整窗口
i=3[1:3,2:−1,3:−3],输出 3下标 1 仍有效
i=4移除 1,尾部依次弹出;[4:5]输出 5

窄屏可左右滑动表格,阅读完整计算与理由。

最大值序列 [3,3,5];队列不是整个窗口,而是未被淘汰的候选。

04为什么这个方法成立

  1. 队列下标递增,确保过期元素只能位于前端。
  2. 队列值递减,被删除的尾部都被更晚且不小的值支配。
  3. 队首既有效又不小于其他候选,因此是当前窗口最大值。

05把推导翻译成代码

Python · 可独立运行的教学实现

from collections import deque
def window_max(a, k):
    if not 1 <= k <= len(a):
        raise ValueError("invalid window")
    q, answer = deque(), []
    for i, x in enumerate(a):
        while q and q[0] <= i-k:
            q.popleft()
        while q and a[q[-1]] <= x:
            q.pop()
        q.append(i)
        if i >= k-1:
            answer.append(a[q[0]])
    return answer

逐个理解关键决定

q[0] <= i-k
窗口左端是 i−k+1,比它小的下标都过期。
a[q[-1]] <= x
相等时保留更晚者,因其存活更久;也可保留两者但需对应的正确规则。

06时间、空间与实现范围

时间 O(n),候选队列 O(k),输出 O(n−k+1)。

deque 两端操作平均 O(1);不要用列表头部删除来实现队列。

07改变条件,检查哪里会出错

每次都清空队列重建

会失去窗口之间复用,退回 O(nk)。

把所有弹出都计成每轮 O(n)

单个下标只入队一次、最多从某一端出队一次,整段操作可以摊还为 O(n)。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

k=1 返回什么?

需要一点提示

每个窗口只有自己。

查看解析与答案

返回原数组各值。

练习 2 · 边界与辨析

严格递减数组的队列多长?

需要一点提示

新值不支配旧值。

查看解析与答案

最多 k,旧值主要从队首过期移除。

练习 3 · 变式与迁移

如何求窗口最小值?

需要一点提示

支配关系反过来。

查看解析与答案

把尾部比较改为 >=,维持递增值队列,队首为最小值。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

MIT 6.006 · 算法讲义

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。