数据结构——单调队列

 顾名思义，单调队列的重点分为 “单调” 和 “队列”

 “单调” 指的是元素的的 “规律”——递增（或递减）
 “队列” 指的是元素只能从队头和队尾进行操作

 先给出一个例子：
 给出一个长度为 n n n的数组，编程输出每 k k k个连续的数中的最大值和最小值。

 最为暴力的做法就是两层循环枚举，时间复杂度是 O ( n ∗ k ) O(n*k) O(n∗k)的。在 n n n较大的情况下回 T L E TLE TLE，如何优化我们的算法是当务之急。

 这时所用到的就是单调队列了。

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

 也就是说——当满足以上条件时，可将前面的数 “弹出”，再将该数真正 p u s h push push进队尾。

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

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

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

 综上所述，单调队列的核心内容作用就在于高效地求出定区间长度内的最值。凭借这个O(n)的高效作用，单调队列这种思想也常用于动态规划等问题中。

inline void monotonous-queue(){
	int head=tail=0;
	for(int i=1;i
		while(head<=tail and a[q[tail]]>=a[i])tail--;
		q[++tail]=i;
	}//先处理前面没有满k个的部分。
	for(int i=k;i<=n;i++){
		while(head<=tail and a[q[tail]]>=a[i])tail--;
		q[++tail]=i;
		while(q[head]<=i-k)head++;
		cout< 
单调队列求最大值 
inline void monotonous-queue(){
	int head=tail=0;
	for(int i=1;i
		while(head<=tail and a[q[tail]]<=a[i])tail--;
		q[++tail]=i;
	}//先处理前面没有满k个的部分。
	for(int i=k;i<=n;i++){
		while(head<=tail and a[q[tail]]<=a[i])tail--;
		q[++tail]=i;
		while(q[head]<=i-k)head++;
		cout<