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

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

下面我會(huì)舉個(gè)簡(jiǎn)單的列子來(lái)解釋單調(diào)隊(duì)列及單調(diào)棧。

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

根據(jù)題意，我們可以得出這樣一個(gè)結(jié)論，若后一個(gè)數(shù)大于前一個(gè)數(shù)，則結(jié)果必定不會(huì)是前一個(gè)數(shù)（比如現(xiàn)在輸入了1，5，由于1<5，所以無(wú)論是后幾個(gè)數(shù)中的最大值均不會(huì)為1），因此，我們只需維護(hù)一個(gè)單調(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同時(shí)7<9因此刪去4添入7，數(shù)組——9,7；輸入——8，由于8>4同時(shí)8<9因此刪去7添入8，數(shù)組——9,8；輸入——6，由于6<8直接添入，數(shù)組——9,8,6。）

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

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

最新評(píng)論