前言

其实单调队列不是真正意义上的队列，它只是一个存在于你脑海里的一个虚拟的队列，虚拟地进行队列的操作。。。（好玄学~~）

0.单调队列思想

单调队列，正如其名，是一个单调的队列，单调递增或者单调递减，所以队首永远是最小值或最大值，这就是单调队列的用处——求一段区间里的最大值或最小值。

1.单调队列操作

通常我们用一个a[]数组存原数组，用一个q[]数组表示单调队列，这个q[]数组存的是队列里元素在原数组里的位置标号（下标）。单调队列与别的队列的原理不太一样，它是在队尾插入元素，在两头删除元素。

下面以一个单调递增队列为例：

入队操作

将要放入队尾的元素e与队尾元素t进行比较，如果e<t,则将t踢出队列，继续拿e与队尾元素比较，直到找到一个元素k<e，把e放在k的后面，至于那些被踢掉的元素。。。就不要了。

出队操作

因为单调队列是要求区间的最小值，所以前面的元素总会有没用的时候，这个时候就要把那些被顶出区间的元素踢掉。

2.单调队列裸题

讲了这么多感觉还是很玄学，那就拿例题来解释吧~~
【题目链接】
洛谷【1440】
【题目描述】
一个含有n项的数列(n<=2000000)，求出每一项前的m个数到它这个区间内的最小值。若前面的数不足m项则从第1个数开始，若前面没有数则输出0。
【输入格式】
第一行两个数n，m。
第二行，n个正整数，为所给定的数列。
【输出格式】
n行，第i行的一个数ai，为所求序列中第i个数前m个数的最小值。
【输入样例】

6 2
7 8 1 4 3 2

【输出样例】

0
7
7
1
1
3

【说明】
数据范围：m≤n≤2000000

【题解】
多么裸的单调队列~~
弄一个单调递增的单调队列，每次输出队首元素a[q[head]]。
有一点要注意的：“所求序列中第i个数前m个数的最小值”.（第一次被坑了）

【程序】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<cstdio>
#include<iostream>
#define M 2000100
using namespace std;
int n,m;
int a[M];                  //原数组 
int q[M];                  //单调队列 
int head=1,tail=1;         //head————头指针，tail————尾指针 
inline void push(int x)
{
	while(head<=tail&&a[x]<=a[q[tail]])    //如果a[x]小于队尾元素，则将队尾元素踢掉，即尾指针前移 
		tail--;
	q[++tail]=x;                           //踢完之后把a[x]放在队尾 
}
inline void pop(int x)
{
	if(q[head]<x-m+1)                      //如果队首元素不在区间里，踢掉它，即头指针后移 
		head++;
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)
		scanf("%d",&a[i]);
	printf("0\n");q[1]=1;              //第一次输出0，题目要求。。。 
	for(int i=2;i<=n;++i)
	{
		printf("%d\n",a[q[head]]);
		push(i);                       //入队 
		pop(i);                        //出队 
	}
	return 0;
}