#学习记录#P1886 滑动窗口 /【模板】单调队列

#思路#

由题意得滑动窗口每次都是舍去第一个元素，新的元素都是在最后加入的，所以考虑使用队列

由于题目要求输出窗口内的最小值和最大值。

队列中存储的是当前元素所对应的序号，用序号来直接访问数组中的元素

最小值：

1. 保证队头都是窗口的最小值
2. 元素只能从队尾进入，当元素是最小值时但是不在窗口内时则需要在队头弹出，当前元素比队尾元素小时从队尾弹出。

最大值与最小值相同。

参考代码：

#include<bits/stdc++.h>
using namespace std;
deque<int>p;
int a[1000000];
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)	cin>>a[i];
	for(int i=1;i<=n;i++){
		while(!p.empty()&&a[p.back()]>a[i])	p.pop_back();//如果队列不为空且队列的最后一项的值比当前的a[i]的值大时则需要将最后的数弹出队列
		p.push_back(i);//每次都将数组的元素加入队列
		if(i>=m){//只有i>=m时才需要输出
			while(!p.empty()&&p.front()<=i-m)	p.pop_front();//判断当前的最小值是否在当前窗口内
			cout<<a[p.front()]<<" ";//最后输出最小值
		}
	}
	cout<<"\n";
	p.clear();//求最大值是记得清空队列中的值
	for(int i=1;i<=n;i++){
		while(!p.empty()&&a[p.back()]<a[i])	p.pop_back();
		p.push_back(i);
		if(i>=m){
			while(!p.empty()&&p.front()<=i-m)	p.pop_front();
			cout<<a[p.front()]<<" ";
		}
	}
	return 0;
} 

学习中的小菜鸡，如果有不对的希望大神指正。