分别维护递增队列和递减队列，用单调队列在线求出每个滑动窗口的最小值和最大值。
OJ: luogu
题目 ID: P1886
难度:普及/提高-
标签:单调队列队列模板题python
日期: 2026-06-18 14:57
题意
给定一个长度为 n 的序列和窗口大小 k。
窗口从左向右每次移动一格，要求输出：
- 每个窗口的最小值
- 每个窗口的最大值
思路
先看最直接的办法：对每个窗口都重新扫描其中的 k 个元素，分别求最小值和最大值。
这个暴力版本很直观：
cpp
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1000000 + 5;
int n, k;
int a[maxn];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int l = 1; l + k - 1 <= n; l++) {
int mn = a[l];
for (int i = l; i < l + k; i++) {
mn = min(mn, a[i]);
}
if (l > 1) {
cout << ' ';
}
cout << mn;
}
cout << '\n';
for (int l = 1; l + k - 1 <= n; l++) {
int mx = a[l];
for (int i = l; i < l + k; i++) {
mx = max(mx, a[i]);
}
if (l > 1) {
cout << ' ';
}
cout << mx;
}
cout << '\n';
return 0;
}但它的复杂度是
这题的关键观察是：
- 如果一个新元素更小，那么队尾那些更大或相等、而且更早进入窗口的元素，以后都不可能再成为最小值；
- 如果一个新元素更大，那么队尾那些更小或相等、而且更早进入窗口的元素，以后都不可能再成为最大值。
所以我们可以分别维护两个存“下标”的单调队列：
qmin：值递增，队头是当前窗口最小值下标；qmax：值递减，队头是当前窗口最大值下标。
每次处理位置 i 时：
- 先把所有已经不在窗口中的下标从队头删掉；
- 再从队尾删掉所有不可能成为未来答案的候选；
- 把当前下标
i入队； - 当
时，队头就是当前窗口答案。
如果你想看更系统的基础讲解，可以参考 rbook 里的《单调队列》： https://rbook2.roj.ac.cn/data_structure/monotonic_queue/index.html
Python 知识
- 正解把百万级原数组、队列下标和答案存进紧凑
array，避免deque[int]的对象内存。 sliding(better)把最小值与最大值的唯一区别抽成比较函数，复用同一单调队列骨架。- 分块输出一行答案，避免同时构造过大的字符串。
代码
python
import os
import sys
from array import array
def read_ints():
number = 0
sign = 1
reading = False
while chunk := os.read(0, 1 << 20):
for byte in chunk:
if 48 <= byte <= 57:
number = number * 10 + byte - 48
reading = True
else:
if reading:
yield sign * number
number = 0
sign = 1
reading = False
elif byte == 45:
sign = -1
if reading:
yield sign * number
data = iter(read_ints())
n, window = next(data), next(data)
values = array("q", (next(data) for _ in range(n)))
def sliding(better):
queue = array("i", [0]) * n
result = array("q")
head = tail = 0
for i, value in enumerate(values):
while head < tail and queue[head] <= i - window:
head += 1
while head < tail and better(value, values[queue[tail - 1]]):
tail -= 1
queue[tail] = i
tail += 1
if i >= window - 1:
result.append(values[queue[head]])
return result
def print_line(sequence):
write = sys.stdout.write
first = True
for start in range(0, len(sequence), 8192):
text = " ".join(map(str, sequence[start:start + 8192]))
write(("" if first else " ") + text)
first = False
write("\n")
print_line(sliding(lambda new, old: new <= old))
print_line(sliding(lambda new, old: new >= old))复杂度
- 时间复杂度：
- 空间复杂度：
总结
单调队列的本质是：只保留窗口里还有机会成为答案的候选。
这道题是最标准的单调队列模板题，关键规则只有两条：
- 过期的从队头删；
- 更差的从队尾删。
一图流解析
这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。
