用单调递减队列保留窗口最大值候选，并以紧凑数组支持两百万规模输入。
OJ: luogu
题目 ID: P2032
难度:普及
标签:单调队列滑动窗口python
创建: 2025-12-26 19:31
更新: 2026-10-07 12:15
前置题目
后置题目
luogu P2216[HAOI2007] 理想的正方形B 把 A 教的「一维单调队列滑窗最值」这一步在横竖两个方向各执行一次合成正方形整体最值（拆成两次一维单调队列），再叠加 A 未教的二维拆解次序与最大减最小的差值目标。luogu P2627[USACO11OPEN] Mowing the Lawn GB 沿用 A 的单调队列窗口最值原语，把候选换成 dp[j-1]-S[j] 做 DP 优化，再叠加断点建模与初始断点入队luogu P1725琪露诺B 把 A 教的「单调队列维护滑动窗口最大值」这一步直接用在 DP 转移 dp[i]=A[i]+max(dp[j]) 的前驱窗口上，再叠加最后一步可越过 N 时用 dp[i] 更新答案的边界处理。luogu P1714切蛋糕先掌握单调队列维护滑动窗口最值。
题意
输出序列中每个长度为
思路
队列保存值严格递减的候选。新数加入时，队尾所有不大于它的旧数更早过期且更小，可以永久删除；队头下标离开窗口时删除。窗口形成后队头就是最大值。
Python 知识
可达两百万，使用两个 array("i")模拟紧凑双端队列，避免大量 Python 元组。os.read分块解析整数，避免read().split()的峰值内存。- 答案按 8192 行分块写出，避免保存全部输出字符串。
代码
python
import os
import sys
from array import array
def read_ints():
number = 0
reading = False
while chunk := os.read(0, 1 << 20):
for byte in chunk:
if 48 <= byte <= 57:
number = number * 10 + byte - 48
reading = True
elif reading:
yield number
number = 0
reading = False
if reading:
yield number
data = iter(read_ints())
n, window = next(data), next(data)
indices = array("i", [0]) * n
values = array("i", [0]) * n
head = tail = 0
output = []
write = sys.stdout.write
for i in range(n):
value = next(data)
while head < tail and indices[head] <= i - window:
head += 1
while head < tail and values[tail - 1] <= value:
tail -= 1
indices[tail] = i
values[tail] = value
tail += 1
if i >= window - 1:
output.append(str(values[head]))
if len(output) == 8192:
write("\n".join(output) + "\n")
output.clear()
if output:
write("\n".join(output) + "\n")复杂度
时间复杂度
总结
滑动窗口最值只需保留尚未过期且没有被更优新元素淘汰的候选。