一、什么是單調棧和單調隊列？

（1）單調棧

從名字上就聽的出來，單調棧中存放的數據應該是嚴格單調有序的，具有以下兩個性質。

1. 滿足從棧頂到棧底的元素具有嚴格的單調遞增或單調遞減性；

2. 滿足棧的后進先出特性，即越靠近棧底的元素越早進棧。

單調棧也分為單調遞增棧和單調遞減棧。

1. 單調遞增棧：單調遞增棧就是從棧底到棧頂數據是從小到大

2. 單調遞減棧：單調遞減棧就是從棧底到棧頂數據是從大到小

單調棧的維護

如何維護一個單調棧？出棧很簡單，與普通棧相同，關鍵操作是入棧。

具體進棧過程

1. 對于單調遞增棧，若當前進棧元素為e，從棧頂開始遍歷元素，把小于e或者等于e的元素彈出棧，直接遇到一個大于e的元素或者棧為空為止，然后再把e壓入棧中。

2. 對于單調遞減棧，則每次彈出的是大于e或者等于e的元素。

于一個元素a，如果?？談t直接入棧。否則比較a與棧頂元素。假設一個單調遞增的棧，若a > 棧頂元素，則直接把a入棧，棧仍滿足單調的性質。若a < 棧頂元素，則將棧頂元素出棧，直到滿足a < 棧頂元素，此時將a入棧。

（2）單調隊列

隊列中元素之間的關系具有嚴格單調有序性，而且，隊首和隊尾都可以進行出隊操作，只有隊尾可以進行入隊操作。因此，在單調隊列中求最值十分容易。

單調隊列與普通隊列有些不同，因為右端既可以插入又可以刪除，因此在代碼中通常用一份數組和rear與rear兩個指針來實現，而不是使用STL中的queue。如果一定要使用STL ，那么則可以使用雙端隊列（即兩端都可以插入和刪除），即deque 。

隊列的大小問題

在談及單調棧時，無需關心棧的大小。而對于隊列，隊列的大小就很重要了。如果隊列滿了，我們的解決方法是，將隊列頭的元素彈出，再添加新的元素到隊列尾。

單調隊列的維護

具體入隊過程

1. 對于單調遞增隊列，設當前準備入隊的元素為e，從隊尾開始把隊列中的元素逐個與e對比，把比e大或者與e相等的元素逐個刪除，直到遇到一個比e小的元素或者隊列為空為止，然后把當前元素e插入到隊尾。

2. 對于單調遞減隊列也是同樣道理，只不過從隊尾刪除的是比e小或者與e相等的元素。

（3）單調棧與單調隊列

單調隊列

1. 可以查詢區(qū)間最值（不能維護區(qū)間k大，因為隊列中很有可能沒有k個元素）；

2. 優(yōu)化DP，單調隊列一般是用于優(yōu)化動態(tài)規(guī)劃方面問題的一種特殊數據結構，且多數情況是與定長連續(xù)子區(qū)間問題相關聯。

單調棧

1. 左邊區(qū)間第一個比它小的數，第一個比它大的數

2. 確定這個元素是否是區(qū)間最值

3. 右邊區(qū)間第一個大于它的值

4. 到右邊區(qū)間第一個大于它的值 的距離

5. 確定以該元素為最值的最長區(qū)間

相同點：

1. 單調隊列和單調棧的“頭部”都是最先添加的元素，“尾部”都是最后添加的元素。

2. 遞增和遞減的判斷依據相同：從棧底（隊尾）到棧頂（隊首），元素大小的變化情況。所以隊列和棧是相反的。

3. 兩者維護的時間復雜度都是O(n)，每個元素都只操作一次。

不同點：

1. 單調隊列可以從隊列頭彈出元素，可以方便地根據入隊的時間順序（訪問的順序）刪除元素。

2. 單調隊列和單調棧維護的區(qū)間不同。當訪問到第i個元素時，單調棧維護的區(qū)間為[ 0 , i )，而單調隊列維護的區(qū)間為( lastpop , i ) 

3. 單調棧無法獲取[ 0 , i )的區(qū)間最大值/最小值。因為單調隊列可以訪問“頭部”和“尾部”，而單調棧只能訪問棧頂（也就是“尾部”）。

二、單調隊列/單調棧優(yōu)化

例題一：單調隊列優(yōu)化

題目描述： 有 n 頭奶牛在一排，每頭奶牛的價值為 vi ，你可以選擇若干頭奶牛，但不能選擇超過 k 頭連續(xù)的奶牛。求價值之和最大為多少。n<=1e5

狀態(tài)設置： f [ i ] ：選擇了若干頭牛，最后一頭牛是第 i 頭牛的最大價值。

問題分析： 顯然，[ i ? k , i ? 1 ] 中有一頭牛不能選，我們可以枚舉這頭牛的位置。

轉移方程：f [ i ] = max ( f [ j ? 1 ] + sum [ i ] ? sum [ j ] ) ， j ∈ [ i ? k , i ? 1 ] 

時間復雜度：

單調隊列優(yōu)化

f [ i ] = max ( f [ j ? 1 ] ? sum [ j ] ) + sum [ i ]， j ∈ [ i ? k , i ? 1 ] 

g [ i ] = f [ i ? 1 ] + sum [ i ] ，維護 g [ i ] 的區(qū)間最大值即可。

補充： 其實可以直接用線段樹維護區(qū)間最值，時間復雜度 O(nlogn)

代碼如下：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
long long f[N];//表示選擇了若干頭牛，最后一頭牛是第 i 頭牛的情況下，的最大價值 
long long g[N];//g[i]=f[i-1]-sum[i] 
long long sum[N],a[N],que[N],head,rear;
int main(){
	int n,k;
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		sum[i]=sum[i-1]+a[i]; 
	}
	long long ans=sum[1];
	f[1]=sum[1];
	g[0]=0;
	g[1]=-sum[1];
	que[rear++]=0;
	que[rear++]=1;
	for(int i=2;i<=n;i++){
		while(head<rear&&i-que[head]>k)head++;//維護范圍限制 
	    f[i]=g[que[head]]+sum[i];//狀態(tài)轉移 
		g[i]=f[i-1]-sum[i];//計算新的要維護的值 
		while(head<rear&&g[i]>g[que[rear-1]])rear--;//加入新的要維護的值 
		que[rear++]=i;
		
		ans=max(ans,f[i]); 
	} 
	cout<<ans;
}

這塊需要大家多多練習，才能更好的靈活運用。