[数据结构与算法]滑动窗口 /【模板】单调队列

滑动窗口 /【模板】单调队列
一个比较简单的知识点，现在补充上

#include <bits/stdc++.h>
using namespace std;
const int MAX=1e6+5;
int a[MAX];
vector<int> mn;
vector<int> mx;

int main() {
	deque<int> q1;
	deque<int> q2;
	int n,k;
	cin>>n>>k;
	for (int i=1;i<=n;i++)
		cin>>a[i];
	for (int i=1;i<=n;i++) {
		while (!q1.empty()&&a[q1.back()]>=a[i]) 
			q1.pop_back();
		while (!q1.empty()&&q1.front()+k<=i)
			q1.pop_front();
		q1.push_back(i);
		if (i>=k)
			mn.push_back(a[q1.front()]); 
	}
	
	for (int i=1;i<=n;i++) { 
		while (!q2.empty()&&a[q2.back()]<=a[i]) 
			q2.pop_back();
		while (!q2.empty()&&q2.front()+k<=i) 
			q2.pop_front();
		q2.push_back(i);
		if (i>=k) 
			mx.push_back(a[q2.front()]);
	}
	
	for (int i=0;i<mn.size();i++)
		cout<<mn[i]<<" ";
	cout<<endl;
	for (int i=0;i<mx.size();i++)
		cout<<mx[i]<<" ";
	return 0;
}