单调队列

参考资料：

OI WIKI

基础概念

单调队列的重点分为 "单调" 和 "队列"

"单调" 指的是元素的的 "规律"——递增（或递减）

"队列" 指的是元素只能从队头和队尾进行操作

\(PS\):此处的 "队列" 跟普通队列的一大不同就在于可以从队尾进行操作，\(STL\)中有类似的数据结构\(deque\)

解题思路

正如基础概念所说的，单调队列与普通队列之区别在于可以在队尾弹出元素，使得可以比较容易的维护其单调性，操作主要如下：

int a[MAXN];//用数组模拟单调队列
int head=0,tail=0;//还没元素

tail++;
cin>>a[tail]//扩展，推入元素

head++;//从队首弹出

tail--;//从队尾弹出

一般单调队列（递减）思路为：

1.入队一个
2.\(for\)循环输入，如果比前面大，则把前面的数从队尾弹出
3.最后输出队首

例题

1.给一个长度为\(n\)的数组，编程输出每\(k\)个连续的数中的最大值和最小值。

这时，很容易想到传统的暴力枚举：对于每一段\(i\) 至 \(i+k-1\)的序列，逐个比较来找出最大值（和最小值），时间复杂度约为\(O(n*k)\),但这种方法在\(k\)稍大的时候就会十分轻易的超时

这时，单调队列闪亮登场！！！

要求的是每连续的 个数中的最大（最小）值，很明显，当一个数进入所要 "寻找" 最大值的范围中时，若这个数比其前面（先进队）的数要大，显然，前面的数会比这个数先出队且不再可能是最大值。

也就是说——当满足以上条件时，可将前面的数 "弹出"，再将该数真正\(push\)进队尾。

这就相当于维护了一个递减的队列，符合单调队列的定义，减少了重复的比较次数，不仅如此，由于维护出的队伍是查询范围内的且是递减的，队头必定是该查询区域内的最大值，因此输出时只需输出队头即可。

显而易见的是，在这样的算法中，每个数只要进队与出队各一次，因此时间复杂度被降到了 。

而由于查询区间长度是固定的，超出查询空间的值再大也不能输出，因此还需要 \(site\)数组记录第\(i\)个队中的数在原数组中的位置，以弹出越界的队头。

2.队员选拔

夏令营马上就要开幕了，学校组织了一次队员选拔活动。参加队员选拔的同学们排队接受面试官们的面试。

他们按照先来先面试并且先结束的原则接受面试官们的考查。

在面试中每位同学的能力值是重点考察指标，作为主面试官的\(John\)想知道当前正在接受面试的同学中能力值最高的人叫什么，他请你帮忙编写一个程序来计算。

第一行一个数字\(N\)，表示操作次数

第\(2\)到\(N+1\)行，每一行表示一个操作，总共有\(3\)种操作，格式如下

C操作
\(Name\) \(Value\)表示名字为\(NAME\)能力值为\(VALUE\)的同学加入面试队列\((|Name|≤10,0≤Value≤10^9|Name|≤10,0≤Value≤10^9)\)

G操作
位于队首的同学离开队列

Q操作
\(John\)想知道当前队列中能力值最高的人的姓名，如果队列为空，输出\(EMPTY\)

对于每一个询问，输出答案，如果多个人拥有最高能力值，请输出最早进队的人的姓名

例题代码

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

int n, a[1000005], q[1000005], front = 1, tail = 1, cur = 0, cnt = 0;
char c, s[1000005][25];

int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++) {
		scanf(" %c", &c);
		if (c == 'G') { //判断操作类型
			cur++; //数的数量++
			if (front < tail && cur >= q[front]) //队不为空且队首元素已经过期，就把队首元素从队首弹出（记住一定是队首，这很重要）
				front++;
		}
		else if (c == 'C') {
			++cnt;
			scanf(" %s %d", s[cnt], &a[cnt]);
			while (front < tail && a[q[tail - 1]] < a[cnt]) //队不为空且新插入的数比前面的数大，就把前面的数挤开
				tail--;//从后面弹出
			q[tail++] = cnt;
		}
		else {
			if (front == tail)
				printf("EMPTY\n");//如果为空
			else
				printf("%s\n", s[q[front]]);//不然输出队首
		}
	}
	return 0;
}