初談這個話題，相信許多人會有一種似有所悟，但又不敢確定的感覺。沒錯，這正是因為其中“單調”一詞的存在，所謂單調是什么，學過函數(shù)的people都知道單調函數(shù)或者函數(shù)的單調性，直白一點說單調就是一直增或一直減。例如：1，3，5，9就是一個單調增數(shù)列，數(shù)列中不存在后一個數(shù)比前一個數(shù)小的現(xiàn)象。那么同樣，在這里談到的話題也有類似特點。

先說一下單調隊列吧!      單調隊列，就是一個符合單調性質的隊列，它同時具有單調的性質以及隊列的性質。他在編程中使用頻率不高，但卻占有至關重要的地位。它的作用很簡單，就是為了維護一組單調數(shù)據(jù)，讓我們在運行的過程中能夠快速尋求前k個或后k個中最大或最小的值。    至于單調棧，相信看完上面的敘述后，都會有一個大概的理解，單調棧就是一個符合單調性質的棧它同時具有單調的性質以及棧的性質。在作用方面兩者是相同的，差別僅是在編程過程中所維護的數(shù)組的方式不同。

下面我會舉個簡單的列子來解釋單調隊列及單調棧。

例題：有一組數(shù)據(jù)1，5，9，4，7，8，6，他們會依此輸入，同時，在某一時刻會讓你求出后n個數(shù)中的最大值。                

根據(jù)題意，我們可以得出這樣一個結論，若后一個數(shù)大于前一個數(shù)，則結果必定不會是前一個數(shù)（比如現(xiàn)在輸入了1，5，由于1<5，所以無論是后幾個數(shù)中的最大值均不會為1），因此，我們只需維護一個單調遞減的數(shù)組便可快速求得所需之。（數(shù)組變化如下：輸入——1，數(shù)組——1；輸入——5，由于5>1刪去1添入5，數(shù)組——5；輸入——9，由于9>5刪去5添入9，數(shù)組——9；輸入——4，由于4<9直接添入，數(shù)組——9,4；輸入——7，由于7>4同時7<9因此刪去4添入7，數(shù)組——9,7；輸入——8，由于8>4同時8<9因此刪去7添入8，數(shù)組——9,8；輸入——6，由于6<8直接添入，數(shù)組——9,8,6。）

單調隊列及單調棧的基礎也就這些，剩下的就只剩下個人理解及練習了。推薦幾道題，在大視野上的1012以及1047，其中1012比較裸適合初學者做，1047略有難度推薦做完1012后再做。（在這里給個提示，1047要用到兩次單調隊列、單調棧，橫著一次再用結果豎這一次。）

以上就是本文的全部內容了，希望對你有所幫助。

最新評論