洛谷 P1886 滑动窗口 /【模板】单调队列_洛谷滑动窗口示例代码

例1.3

#include<iostream>
#include<deque>
using namespace std;
 
const int max_n = 1e6 + 5;
int a[max_n];//序列a
deque<int> q;//窗口队列,其中的数据是元素在a序列中的位置
 
int main() {
	int n, k;
	cin >> n >> k;
 
	//初始化序列a
	for (int i = 1; i <=n; i++) {
		cin >> a[i];
	}
 
	//每个窗口的最小值
	for (int i = 1; i <= n; i++) {
 
		//保证第i个数加入窗口时保证末尾数字最大
		while (!q.empty() && a[q.back()] > a[i]) q.pop_back();
 
		q.push_back(i);
 
		//窗口开始滑动
		if (i >= k) {
			//对列头的数字超过窗口的范围，弹出
			while (!q.empty() && i-q.front()>=k ) q.pop_front();
 
			cout << a[q.front()] << " ";
		}
	}
 
	//清空窗口队列
	q.clear();
	cout << endl;
 
	//每个窗口的最大值
	for (int i = 1; i <= n; i++) {
		//保证第i个数加入窗口时保证末尾数字最小
		while (!q.empty() && a[q.back()] < a[i])q.pop_back();
		q.push_back(i);
		//窗口开始滑动
		if (i >= k) {
			//对列头的数字超过窗口的范围，弹出
			while (!q.empty() && i - q.front() >= k)q.pop_front();
			cout << a[q.front()] << " ";
		}
	}
}