P1886 滑动窗口
对应章节：一、C++ 语法基础 → （十五） STL：容器、迭代器与算法。
（一） 任务与输出目标
输出每个长度为 k 的连续窗口的最小值和最大值。
（二） 建模与推导
队列保存候选下标，从前到后值递增。新值 x 到来时，队尾中不小于 x 的旧值可以移除：x 更小且位置更晚，以后的窗口中旧值能出现时，x 也能出现。队头过期就移除；留下的队头是最小值。求最大值时反向比较即可。
本题窗口包含当前项，先把它加入，再在窗口长度达到 k 时输出。
（三） 手算与过程
a=3,1,2,0，k=2：窗口 3,1 → 1,2 → 2,0；最小值为 1,1,0，最大值为 3,2,2。
（四） 带注释实现
#include <bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
void solve() {
int n, k;
cin >> n >> k;
vector<int> a(n);
for (int& x : a)
cin >> x;
deque<int> low, high;
vector<int> minimum, maximum;
for (int i = 0; i < n; ++i) {
while (!low.empty() && low.front() <= i - k)
low.pop_front();
while (!high.empty() && high.front() <= i - k)
high.pop_front();
while (!low.empty() && a[low.back()] >= a[i])
low.pop_back(); // 更大更旧的候选被支配。
while (!high.empty() && a[high.back()] <= a[i])
high.pop_back();
low.push_back(i);
high.push_back(i);
if (i + 1 >= k) {
minimum.push_back(a[low.front()]);
maximum.push_back(a[high.front()]);
}
}
for (int x : minimum)
cout << x << ' ';
cout << '\n';
for (int x : maximum)
cout << x << ' ';
cout << '\n';
}
signed main() {
ios::sync_with_stdio(false); // 关闭同步，使用 cin 与 cout 完成输入输出。
cin.tie(0), cout.tie(0);
int T = 1; // 本题读入一组数据。
// cin >> T; // 题目给出测试组数时开启，并在 solve 中处理一组。
while (T--)
solve();
}（五） 复杂度
每个下标入队一次、从两端合计移除至多一次，时间 \(O(n)\)；存入数据和输出占 \(O(n)\)，候选队列占 \(O(k)\)。