P1886 滑动窗口 /【模板】单调队列 – 洛谷 | 计算机科学教育新生态

#include<bits/stdc++.h>
using namespace std;
int n,k;

deque<int> q;//定义一个双端队列
int main()
{
	cin>>n>>k;
	vector<int> a(n+1);
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=n;i++){
		while(q.size()&&a[i]<a[q.back()]) q.pop_back();//判断此时的队列尾端是否比前面的小 如果小的话就证明以后不会再用到前面的那个数 所以将他踢出双端队列
		
		q.push_back(i);//输入数组下标到双端队列中
		if(i>=k){
			while(q.size()&&q.front()<=i-k) q.pop_front();
			cout<<a[q.front()]<<" ";	//判断队列是否满足输出的条件 因为双端队列存储的下标在数组中是从小到大的如果最开始的那个不满足条件就直接踢出双端队列 满足条件就输出  以上的操作保证双端数列的最前面是最小的数 同时又会判断出此下标是否满足条件
		}
	}
	cout<<endl;
	q.clear();//清空数组
	for(int i=1;i<=n;i++){
		while(q.size()&&a[i]>a[q.back()]){
			q.pop_back();
		}
		q.push_back(i);
		if(i>=k){
			while(q.size()&&q.front()<=i-k) q.pop_front();
			cout<<a[q.front()]<<" ";
		}
	}
	return 0;
}

双端队列（deque）的概述补充

双端队列（deque，double-ended queue）是一种允许在两端高效插入和删除的容器。它兼具队列和栈的特性，具有以下特性：

• 在双端队列的头部和尾部插入和删除元素的时间复杂度都是 O(1)O(1)O(1)。
• 它既可以像栈一样在一端进行后进先出的操作，也可以像队列一样在一端进行先进先出的操作。

在 C++ 中，deque 是 STL 提供的一种容器，通常用于需要两端操作的场景，常用的成员函数包括：

• push_back(val): 在队尾添加元素 val
• push_front(val): 在队首添加元素 val
• pop_back(): 移除队尾的元素
• pop_front(): 移除队首的元素
• front(): 获取队首元素
• back(): 获取队尾元素
• size(): 获取队列当前元素个数
• clear(): 清空队列