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

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

下面我會舉個簡單的列子來解釋單調(diào)隊列及單調(diào)棧。

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

根據(jù)題意，我們可以得出這樣一個結(jié)論，若后一個數(shù)大于前一個數(shù)，則結(jié)果必定不會是前一個數(shù)（比如現(xiàn)在輸入了1，5，由于1<5，所以無論是后幾個數(shù)中的最大值均不會為1），因此，我們只需維護一個單調(diào)遞減的數(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。）

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

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

最新評論