题目链接：

题意：

给 n, k，n 个数字，求所有长度为 k 的区间的最小值和最大值

做法：

单调队列，考虑维护一个单调递增/减的队列，并用滑动窗口的方法使得队列的首尾位置相差<=k，这样每次队首的位置都是长度为 k 的区间的最大/小值

代码： 

#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
deque<int>q1, q2;
//q1 单调增   q2 单调减
int a[1000005];
int main()
{
	int n, k, t;
	sc("%d%d", &n, &k);
	vector<int>ans1, ans2;
	for (int i = 1; i <= n; i++)
	{
		sc("%d", &a[i]);
		while (!q1.empty() && q1.front() + k <= i)
			q1.pop_front();
		while (!q1.empty() && a[q1.back()] > a[i])
			q1.pop_back();

		while (!q2.empty() && q2.front() + k <= i)
			q2.pop_front();
		while (!q2.empty() && a[q2.back()] < a[i])
			q2.pop_back();

		q1.push_back(i);
		q2.push_back(i);

		if (i >= k)
		{
			ans1.push_back(a[q1.front()]);
			ans2.push_back(a[q2.front()]);
		}
	}
	for (int i = 0; i <= n - k; i++)
		pr("%d%c", ans1[i], i == n - k ? '\n' : ' ');
	for (int i = 0; i <= n - k; i++)
		pr("%d%c", ans2[i], i == n - k ? '\n' : ' ');
}