AcWing 154. 滑动窗口

题面：
给定一个大小为 \(n≤10^6\) 的数组。
有一个大小为 \(k\) 的滑动窗口，它从数组的最左边移动到最右边。
你只能在窗口中看到 \(k\) 个数字。
每次滑动窗口向右移动一个位置。
你的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。

原题链接：154. 滑动窗口 - AcWing

#include <bits/stdc++.h>
using namespace std;

const int N = 1000005;
int a[N], n, k;

int main()
{
	deque<int> q;	//双端队列
	cin >> n >> k;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	//先求最小值，即单增队列
	for (int i = 1; i <= n; i++) {
		//当队尾元素大于当前值时，因为窗口从左往右滑动，队尾不可能成为最小值，故出队
		while (q.size() && q.back() > a[i])
			q.pop_back();
		q.push_back(a[i]);
		//当队元素满k个或队头在k个数之前，即队头元素在窗口外，队头出队
		if (i - k >= 1 && q.front() == a[i - k])
			q.pop_front();
		//前三个数已经被输入，窗口形成，开始输出队头对应的值
		if (i >= k)
			cout << q.front() << " ";
	}
	q.clear();
	cout << endl;

	//最大值同理
	for (int i = 1; i <= n; i++) {
		while (q.size() && q.back() < a[i])
			q.pop_back();
		q.push_back(a[i]);
		if (i - k >= 0 && q.front() == a[i - k])
			q.pop_front();
		if (i >= k)
			cout << q.front() << " ";
	}
}