一、前言
今天总结的一个东西叫做单调队列，其实单调队列这个名字一听就知道是跟数据结构有关。而之所以命名为这个，肯定说明了他代表队列里面的元素都是成为一个单调的形式存在在队列中的。今天主要介绍两种实现单调队列的方法吧。
首先考虑这样的一个题目：这是洛谷的P1886滑动窗口单调队列。
①题目描述如下：
数据范围为：$1 <= n <= k <= 10^6$。
②解题思路
我们不妨以求某个窗口的最小值为例子(最大值同理也可以那么推导)。我们首先做的事情就是，依次的放入元素，到一个我们设置好的队列之中，因为这个队列要满足最后输出的结果是最小值，此时我们的队列应当满足单调递增的顺序，这样的话我们每次输出的结果就是在输出一个队首的元素，保证输出的结果是在队列里面是最小的。那么一旦我即将要入队的元素比我目前队尾的元素要小的话，那么队尾会直接弹出，这是因为队尾元素和即将入队的元素已经在一个窗口里面了，由于即将入队的元素小，那么肯定就会有此滑动窗口元素的最小值不可能是原先队尾的元素了。如果当队首元素的下标已经不包含在滑动窗口里面的话，那么我们要进行一个队首出队的行为，保证后面答案的更新不包括滑动窗口以外的元素！
③一些问题及举例说明
1.为什么队列要满足单调递增呢？
我们考虑题目中的样例，当我们1入队以后，3能不能入队呢？答案是能。因为我们无法保证3之后的数字会不会比3还大，假设3之后的数字是4，5，6，……，那么当我们输出第一个答案1之后，滑动窗口往后移动，此时最小值就是3了，所以保证队列是单调递增的。
2.如何去判断队首元素不在滑动窗口里面呢？
要判断队首元素在不在窗口，就是说其坐标是不是比窗口的左边边界要大。这就需要我们另外用方法记录下来队首元素的坐标，比如开一个数组进行坐标的记录。假设我们遍历到第i个元素了，那么滑动窗口的左边界其实就是(i - k),此时就判断他是否比队首元素坐标小就好，如果不是，就让队首元素弹出就好了。
二、实现方法1(数组模拟)
其实数组模拟了一个比较底层的数据结构deque,也就是双向队列。这个队列之所以能够满足题目的要求，就是因为，队首和队尾元素都可以进行弹出的操作，也就像一个管道一样，你可以从管道的两头出去，而不仅仅像一个队列一样，只能队首进行弹出。
以下代码有相关注释，结合前言，大家可以试着走一下程序。
AC代码
#include<bits/stdc++.h>
using namespace std;
const int N = 1e+6 + 5;
int nums[N];
int q[N]; //队列
int p[N]; //下标
int main() {
int n, k;
cin >> n >> k;
int head, tail;
for(int i = 0; i < n; i++) {
cin >> nums[i];
}
//输出滑动窗口最小值
head = 0, tail = -1;
for(int i = 0; i < n; i++) {
//如果入队元素比队尾大，就队尾出队
while(head <= tail && q[tail] >= nums[i])
tail--;
//入队操作
q[++tail] = nums[i];
p[tail] = i;
//如果滑动窗口不包括队首元素，队首出队
if(head <= tail && i - k >= p[head])
head++;
//进行输出
if(i - k + 1 >= 0) cout << q[head] <<" ";
}
cout << endl;
//输出滑动窗口最大值
memset(q, 0, sizeof(q));
memset(p, 0, sizeof(p));
head = 0, tail = -1;
for(int i = 0; i < n; i++) {
//如果入队元素比队尾大，就队尾出队
while(head <= tail && q[tail] <= nums[i])
tail--;
//入队操作
q[++tail] = nums[i];
p[tail] = i;
//如果滑动窗口不包括队首元素，队首出队
if(head <= tail && i - k >= p[head])
head++;
//进行输出
if(i - k + 1 >= 0) cout << q[head] <<" ";
}
}三、实现方法2(deque)
我们可以直接用STL自带的deque底层队列进行模拟，这个地方，可以重新设置一下类，然后让队列的入队出队方式有一些细微的变化。这里的代码仅供参考，也是能过的，当然会稍微有点难理解吧,因为用到类和函数重置的相关知识了！
下面代码依次拼在一起就是最终的AC代码啦！
不知道为什么这里的代码不给我放到代码块里面，所以为了有更好的观感，可以去我的CSDN里面看这篇文章！
#include<bits/stdc++.h>
using namespace std;
int nums[10000005];
//实现最大值的获取
class myqueuemax
{
public:
dequeque1;
void pop(int value)
{
//如果队首元素已经不在滑动窗口才弹出
if(!que1.empty()&&value==que1.front())
que1.pop_front();
}
void push(int value)
{
//加入的元素是否比队尾大就弹出队尾，保证单调递减
while(!que1.empty()&&value>que1.back())
que1.pop_back();
que1.push_back(value);
}
int front()
{
return que1.front();
}
};//实现最小值的获取
class myqueuemin
{
public:
dequeque2;
void pop(int value)
{
//如果队首元素已经不在滑动窗口才弹出
if(!que2.empty()&&value==que2.front())
que2.pop_front();
}
void push(int value)
{
//加入的元素是否比队尾大就弹出队尾，保证单调递增
while(!que2.empty()&&value<que2.back())
que2.pop_back();
que2.push_back(value);
}
int front()
{
return que2.front();
}
};int main()
{
myqueuemax que1;
myqueuemin que2;
int k,n;
cin>>n>>k;
//最小值的输出
for(int i=0;i<n;i++)
{
cin>>nums[i];
}
for(int i=0;i<k;i++)
{
que2.push(nums[i]);
}
cout<<que2.front()<<” “;
for(int i=k;i<n;i++)
{
que2.pop(nums[i-k]); //直接利用下标对应的元素判断队首是否还在队列中
que2.push(nums[i]);
cout<<que2.front()<<” “;
}
cout<<endl;
//最大值的输出
for(int i=0;i<k;i++)
{
que1.push(nums[i]);
}
cout<<que1.front()<<” “;
for(int i=k;i<n;i++)
{
que1.pop(nums[i-k]); //直接利用下标对应的元素判断队首是否还在队列中
que1.push(nums[i]);
cout<<que1.front()<<” “;
}
}
