单调队列

单调队列能够保证最大/最小的元素始终出现在队首，同时维持原先数据的顺序。实现单调队列需要用到deque双向队列。

每当获取到一个元素时，弹出前方所有比它小的元素，从而保证队列的单调性；每当最大/最小元素，即队首离开窗口时，则将其弹出队列。

单调队列可以用于解决滑动窗口问题。

滑动窗口问题

有一个长为n的序列a，以及一个大小为k的窗口。现在这个从左边开始向右滑动，每次滑动一个单位，求出每次滑动后窗口中的最大值和最小值。

本题通过分别生成单调递增队列和单调递减队列得到所需结果。完整代码见下：

#include<bits/stdc++.h>
using namespace std;

struct Node
{
	long long id, value;
}node[1000010];

deque<Node> dq;
int n,k;

int main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)
	{
		cin>>node[i].value;
		node[i].id=i;
		while(dq.size()!=0 && node[i].value<dq.front().value)
		{
			dq.pop_front();
		}
		while(dq.size()!=0 && node[i].value<dq.back().value)
		{
			dq.pop_back();
		}
		dq.push_back(node[i]);
		if(i-dq.front().id>k-1) dq.pop_front();
		if(i>=k) cout<<dq.front().value<<" ";
	}
	cout<<endl;
	dq.clear();
	
	for(int i=1;i<=n;i++)
	{
		node[i].id=i;
		while(dq.size()!=0 && node[i].value>dq.front().value)
		{
			dq.pop_front();
		}
		while(dq.size()!=0 && node[i].value>dq.back().value)
		{
			dq.pop_back();
		}
		dq.push_back(node[i]);
		if(i-dq.front().id>k-1) dq.pop_front();
		if(i>=k) cout<<dq.front().value<<" ";
	}
	return 0;
}

附 C++ deque API：

1. dq.front():返回的一个元素的引用。
2. dq.back():返回最后一个元素的引用。
3. dq.pop_back():删除尾部的元素。不返回值。
4. dq.pop_front()：删除头部元素。不返回值。
5. dq.push_back(e):在队尾添加一个元素e。
6. dq.push_front(e):在对头添加一个元素e。