單調隊列模板【附例題】

其實單調隊列就是一種隊列內的元素有單調性的隊列，因為其單調性所以經常會被用來維護區間最值或者降低DP的維數已達到降維來減少空間及時間的目的。

每一個答案只與當前下標的前m個有關，所以可以用單調隊列維護前m的個最小值，

考慮如何實現該維護的過程？？

顯然當前下標\(X\)的\(m\)個以前的元素（即下標小於\(X-M+1\)的元素）在範圍外，和答案沒什麼太大聯繫，所以可以將其從隊列中刪除。

對於兩個元素\(A\)，\(B\)，下標分別為\(a\),\(b\)，如果有\(A>=B\)&&\(a<b\)那麼B留在隊列里肯定優於\(A\)，因此可以將\(A\)刪除。

維護隊首：如果隊首已經是當前元素的\(m\)個之前，將\(head\)++，彈出隊首元素

維護隊尾：比較\(q[tail]\)與當前元素的大小，若當前元素更優\(tail\)++，彈出隊尾元素，直到可以滿足隊列單調性後加入當前元素。

考慮單調隊列的時間複雜度：由於每一個元素只會進隊和出隊一次，所以為\(O(n)\)。

P1440 求m區間內的最小值

P1886 滑動視窗 /【模板】單調隊列

P3088[USACO13NOV]Crowded Cows S

#include <bits/stdc++.h>
using namespace std;
int a[2000100];
bool b[2000100];
int q[2000100];//數組模擬隊列，更好調試
int head=1,tail=0;
int n,m;
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
	}
	for(int i=1;i<=n;i++)
	{
		while(i-q[head]+1>m&&head<=tail)//若頭結點在範圍外 
		{
			head++;//彈出頭結點 
		}
		while(a[i]<a[q[tail]]&&head<=tail)//若當前節點優於尾節點 
		{
			tail--;//彈出尾結點 
		}
		q[++tail]=i;//當前節點入隊 
	}
	return 0;
}

利用單調隊列，可以優化涉及定長連續子區間求最值的線性dp問題

例題

P1725 琪露諾 琪露諾是最強的！！