單調隊列模闆+例題

單調隊列是指：隊列中元素之間的關系具有單調性，而且，隊首和隊尾都可以進行出隊操作，隻有隊尾可以進行入隊操作。

單調隊列顧名思義就是一個有規律的隊列，這個隊列的規律是：所有在隊列裡的數都必須按遞增（或遞減）的順序列隊。

例如：

有如下一串數字：1 5 3 4 2

首先第一個數字1先進隊列，que = {1}；

之後第二個數字5大于1，則1出隊列5進隊列，que = {5}；

下一步第三個數字3小于5，進隊列，que = {5，3}；

下一步第四個數字4大于3，則3出隊列4進隊列，que = {5，4}；

下一步第五個數字2小于4，進隊列，que = {5，4，2}；

這樣最後隊列裡的數字為單調遞減排列。

模闆:

//que數組存儲資料在a數組中的下标

que[++tail] = 1;//第一個資料先進入隊列
for(int i = 2; i <= n; i++){
	while(head <= tail && i - que[head] == k)//判斷最大的數是否在範圍之内，若不在則出隊列
		head++;
	while(head <= tail && a[i] >= a[que[tail]])//當新插入的數比隊尾大時，彈出隊尾的數
		tail--;
	que[++tail] = i; //新插入的數進入隊列
	if(i >= k)
		printf("%d\n", a[que[head]]);
	}
           

例題：

洛谷2032掃描

#include<stdio.h>
#define maxn 2000001
int head = 1, tail = 0;
int a[maxn], que[maxn];

int main(){
	int n, k;
	scanf("%d %d", &n, &k);
	for(int i = 1; i <= n; i++){
		scanf("%d", &a[i]);
	}
	//單調隊列遞減，則隊頭為最大元素
	que[++tail] = 1;
	for(int i = 2; i <= n; i++){
		while(head <= tail && i - que[head] == k)//判斷最大的數是否在範圍之内，若不在則出隊列
			head++;
		while(head <= tail && a[i] >= a[que[tail]])//當新插入的數比隊尾大時，彈出隊尾的數
			tail--;
		que[++tail] = i; //新插入的數進入隊列
		if(i >= k)
		    printf("%d\n", a[que[head]]);
	}
	return 0;
}