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为什么这个方法成立
- 队列下标递增,确保过期元素只能位于前端。
- 队列值递减,被删除的尾部都被更晚且不小的值支配。
- 队首既有效又不小于其他候选,因此是当前窗口最大值。
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从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
k=1 返回什么?
需要一点提示
每个窗口只有自己。
查看解析与答案
返回原数组各值。
严格递减数组的队列多长?
需要一点提示
新值不支配旧值。
查看解析与答案
最多 k,旧值主要从队首过期移除。
如何求窗口最小值?
需要一点提示
支配关系反过来。
查看解析与答案
把尾部比较改为 >=,维持递增值队列,队首为最小值。