单调队列维护窗口极值

数学 / 逻辑形态

deque 索引按位置递增、对应值按目标方向单调。处理 i 时先/后清除 index≤i-k 的过期头，并从尾部弹出不优于 a[i] 的候选，再压 i。

识别信号

每个长度 k 窗口都要最大值或最小值。
候选既会因更优新值被支配，也会因离开窗口而失效。
需要优化形如 dp[i]=best(dp[j])+cost 的有限回看转移。
堆可做但 lazy 过期有 log k 成本。

容易误判的相似信号

Signal	Why it is different
最近更大元素	没有窗口过期时单调栈更直接。
窗口和/频次	可逆聚合用普通滑窗即可，不需要支配淘汰。

核心不变量

deque 中索引严格递增且都在当前窗口内；其值按目标方向单调，队首是当前窗口极值，每个被尾弹的索引在未来共同窗口中永不优于新索引。

状态、转移与处理顺序

Item	Definition
State	索引 deque、当前 i、窗口宽 k，以及输出/DP。
Transition	移除队首过期索引；从队尾弹出被当前值支配者；压入 i；窗口成熟后读取队首值。
Frontier / order	当前窗口内仍有可能在现在或未来成为极值的 Pareto 候选链。

Python 骨架

from collections import deque

def window_max(values, k):
    if k <= 0 or k > len(values):
        return []
    dq, answer = deque(), []
    for i, value in enumerate(values):
        while dq and dq[0] <= i - k:
            dq.popleft()
        while dq and values[dq[-1]] <= value:
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            answer.append(values[dq[0]])
    return answer

正确性思路

过期清理保证 deque 中每个索引属于当前窗口。
若旧候选值≤新值且位置更早，它会更早过期且从不更优，因此尾弹安全。
剩余值单调，队首既未过期又不被任何候选支配，正是窗口最大值。

复杂度

Time	Space	Parameters
O(n)	O(k)	每个索引入队一次，从头或尾出队至多一次；deque 最多保存窗口内 k 个索引。

边界条件

k=1 时输出等于输入。
k=n 时只有一个极值。
k 非法时返回契约需明确。
重复值用 <= 尾弹可保留较新的等值索引，更晚过期。

错误模式

Pattern	Why it fails / fix
deque 存值不存索引	无法判断何时过期，重复值也难区分。
过期条件写成 < i-k	索引 i-k 已不在 [i-k+1,i]，应使用 <=。
把尾部单调方向写反	求最大值应从尾部移除不大于新值的候选。

选择与排除规则

连续固定窗的 min/max：单调 deque。
只需最近支配边界、没有 k：单调栈。
候选排序依据复杂且不能用单值支配：考虑 heap。

Relation	Template	Boundary
极值状态组件	定长滑动窗口	固定窗统计从可逆和升级到不可逆 min/max。
极值/前缀边界增强	可变长滑动窗口	需在窗口内维护极值或选择最优历史前缀。
有序候选替代	Top-K 有界堆	需要多个优先级候选而非单调支配链。
同数据结构不同不变量	0-1 BFS	勿把优先级 deque 与窗口极值 deque 混为一谈。

原创微型例子

环节	内容
Result	两个窗口最大值为 [3,3]。
Setup	值 [2,1,3,2]，k=3，求每窗最大值。
Trace	到 3 时从尾部弹 1、2，只留索引 2；下一步加入 2 但 3 仍在队首。

Recall prompts

为什么队列里必须存索引？
尾部被新值支配为何可永久删除？
过期阈值 i-k 对应哪个窗口左端？

单调队列维护窗口极值

数学 / 逻辑形态

识别信号

容易误判的相似信号

核心不变量

状态、转移与处理顺序

Python 骨架

正确性思路

复杂度

边界条件

错误模式

选择与排除规则

相关模板

原创微型例子

Recall prompts

我的补充