隊(duì)列和棧是很常見的應(yīng)用，大部分算法中都能見到他們的影子。

　　而單純的隊(duì)列和棧經(jīng)常不能滿足需求，所以需要一些很神奇的隊(duì)列和棧的擴(kuò)展。

　　其中最出名的應(yīng)該是優(yōu)先隊(duì)列吧我覺得，然后還有兩種比較小眾的擴(kuò)展就是單調(diào)隊(duì)列和單調(diào)棧。

?

　　先來看一個(gè)問題，給一個(gè)長度為N的數(shù)列，a1，a2。。。aN，然后給一個(gè)k<=N，求輸出b1，b2。。。bN這N個(gè)數(shù)，其中 bi=max( aj | j<=i && j>i-k && j>0 )。

　　比較樸素的想法是用一個(gè)Nk復(fù)雜度的循環(huán)來求，但是這樣的話如果N很大的話就太慢了。

　　然后還有一種想法是維護(hù)一個(gè)BST，然后for循環(huán)從左到右，依次加入到BST里面，如果某個(gè)數(shù)超出了k的范圍，就從BST中刪除。

　　偽代碼如下：

1 void getans() { 2 BST tree; 3 4 for(int i=1,j=1;i<=N;++i) { 5 tree.insert(a[i]); 6 while(j<=i-k) { 7 tree.erase(a[j]); 8 --j; 9 } 10 cout<<tree.max()<<endl; 11 } 12 }

　　這樣的話因?yàn)槊總€(gè)數(shù)只insert一次，最多erase一次，所以復(fù)雜度是NlogN的，已經(jīng)很不錯(cuò)了。

?

　　但是BST比較高級，所以速度并不快，那么能不能根據(jù)這個(gè)問題的特點(diǎn)來設(shè)計(jì)一種更快的數(shù)據(jù)結(jié)構(gòu)來解決？

　　先看這個(gè)問題，如果for循環(huán)從左到右來求b的話，就像是有個(gè)長度為k的框框一次次向右移動，每次求框內(nèi)的最大值。

　　

　　如果類比到隊(duì)列的話，就是for循環(huán)的時(shí)候每次push一個(gè)數(shù)在隊(duì)尾，然后把最前面那個(gè)超出的數(shù)pop出來，然后求隊(duì)列內(nèi)的最大值就行了。

　　但是一般的隊(duì)列并不能求最大值，就需要一些擴(kuò)展型的隊(duì)列了。

?

　　單調(diào)隊(duì)列就是隊(duì)列內(nèi)所有數(shù)都是單調(diào)遞增的或者遞減的。下面按照從隊(duì)首到隊(duì)尾遞減的隊(duì)列來討論。

　　先看看push(x)：

　　　　如果當(dāng)前隊(duì)列為空的話，直接push進(jìn)去就行。

　　　　如果當(dāng)前隊(duì)列末尾的數(shù)比x大，那么直接放到隊(duì)尾，這時(shí)仍然是單調(diào)的。

　　　　如果末尾的數(shù)比x小的話，就扔掉隊(duì)尾的數(shù)，然后再重復(fù)上面的步驟push(x)。

　　　　比如隊(duì)列中是 ?5 4 2 1，然后push 3 進(jìn)去的話，就把1和2扔掉，變成5 4 3，如果再push 7 進(jìn)去的話，就把5 4 3 扔掉，隊(duì)列變成了 7 。

　　然后pop的話和一般隊(duì)列沒有區(qū)別。

?

　　然后這個(gè)數(shù)據(jù)結(jié)構(gòu)如果應(yīng)用到這個(gè)問題上的話，看看答案是否是對的。

　　for循環(huán)從左到右，然后每次push當(dāng)前的ai，然后判斷如果隊(duì)首的元素的位置超出了框框，就pop出來扔掉。然后這是bi就等于pop完之后隊(duì)首的數(shù)。

1 struct Queue { 2 int val[MaxN],pos[MaxN]; 3 int first,last; 4 5 void init() { 6 first=last=0; 7 } 8 9 void push(int v,int p) { 10 while(last-first>0 && val[last-1]<=v) --last; 11 val[last]=v; 12 pos[last++]=p; 13 } 14 15 void pop() { 16 if(last-first>0) ++first; 17 } 18 19 int firstPos() { 20 return pos[first]; 21 } 22 23 int firstVal() { 24 return val[first]; 25 } 26 }; 27 28 void getans() { 29 Queue que; 30 que.init(); 31 32 for(int i=1;i<=N;++i) { 33 que.push(a[i],i); 34 while(que.firstPos()<=i-k) que.pop(); 35 cout<<que.firstVal().val<<endl; 36 } 37 }

?

　　先來看看這樣對不對，首先隊(duì)列是單調(diào)的，所以隊(duì)首的數(shù)一定是最大的，這個(gè)數(shù)在失效的時(shí)候，在他位置前面的所有數(shù)也一定都失效了，而他位置后面的所有數(shù)還沒失效，仍然符合最大的前面，也就是最大的仍然還在隊(duì)列中沒有被扔掉。所以下一次詢問的時(shí)候仍然答案是對的。

?

　　然后看看復(fù)雜度如何，每個(gè)數(shù)只push了一次，然后最多會被扔掉一次，所以雖然push里面有while循環(huán)，但是這N個(gè)數(shù)每個(gè)最多被遍歷一次然后就被扔掉了，所以for循環(huán)N次下來，均攤的復(fù)雜度是O（1）的對于每個(gè)push和pop操作，所以總復(fù)雜度是O（N）的。

?

?

　　然后這就是單調(diào)棧，單調(diào)棧和單調(diào)隊(duì)列區(qū)別不大，都是每次push的時(shí)候要維護(hù)單調(diào)性。

　　有一道題目 POJ 2796?，需要先進(jìn)行轉(zhuǎn)化然后在使用單調(diào)棧來解決。

?

　　單調(diào)棧和單調(diào)隊(duì)列在大部分情況下是一種工具，對于一些問題能夠優(yōu)化到N的復(fù)雜度，這樣會比logN快很多。所以其實(shí)有些情況下不用這個(gè)，用其他的數(shù)據(jù)結(jié)構(gòu)也是可以做的。

轉(zhuǎn)載于:https://www.cnblogs.com/whywhy/p/5066306.html

總結(jié)

以上是生活随笔為你收集整理的数据结构录 之 单调队列单调栈。的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。