淺談單調(diào)隊(duì)列、單調(diào)棧
初談這個(gè)話題，相信許多人會(huì)有一種似有所悟，但又不敢確定的感覺。沒錯(cuò)，這正是因?yàn)槠渲小皢握{(diào)”一詞的存在，所謂單調(diào)是什么，學(xué)過函數(shù)的people都知道單調(diào)函數(shù)或者函數(shù)的單調(diào)性，直白一點(diǎn)說單調(diào)就是一直增或一直減。例如：1，3，5，9就是一個(gè)單調(diào)增數(shù)列，數(shù)列中不存在后一個(gè)數(shù)比前一個(gè)數(shù)小的現(xiàn)象。那么同樣，在這里談到的話題也有類似特點(diǎn)。
先說一下單調(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)行的過程中能夠快速尋求前k個(gè)或后k個(gè)中最大或最小的值。 至于單調(diào)棧，相信看完上面的敘述后，都會(huì)有一個(gè)大概的理解，單調(diào)棧就是一個(gè)符合單調(diào)性質(zhì)的棧它同時(shí)具有單調(diào)的性質(zhì)以及棧的性質(zhì)。在作用方面兩者是相同的，差別僅是在編程過程中所維護(hù)的數(shù)組的方式不同。
下面我會(huì)舉個(gè)簡(jiǎn)單的列子來解釋單調(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，所以無論是后幾個(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ì)你有所幫助。
相關(guān)文章
這篇文章主要介紹了C++內(nèi)存分布及用法，從內(nèi)存的基礎(chǔ)概念到內(nèi)存分配進(jìn)行了講解，內(nèi)存是我們開發(fā)中最重要的一部分，往往邏輯上的錯(cuò)誤就會(huì)造成內(nèi)存泄漏，導(dǎo)致程序無法運(yùn)行，下面我們就來了解文章對(duì)該內(nèi)容的詳細(xì)介紹2021-12-12
C/C++函數(shù)調(diào)用棧的實(shí)現(xiàn)方法
這篇文章主要介紹了C/C++函數(shù)調(diào)用棧的實(shí)現(xiàn)方法,可實(shí)現(xiàn)一個(gè)簡(jiǎn)單的腳本解釋器,具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2014-10-10
這篇文章主要為大家詳細(xì)介紹了C++中值傳遞、指針傳遞和引用傳遞的定義與使用，文中的示例代碼講解詳細(xì)，對(duì)我們學(xué)習(xí)C++有一定幫助，需要的可以參考一下2022-10-10
C語言詳細(xì)解析有符號(hào)數(shù)與無符號(hào)數(shù)的表示
我們知道，在C語言中存在無符號(hào)數(shù)和有符號(hào)數(shù)，但是對(duì)于計(jì)算機(jī)而言，其本身并不區(qū)別有符號(hào)數(shù)和無符號(hào)數(shù)，因?yàn)樵谟?jì)算機(jī)里面都是O或者1，但是在我們的實(shí)際使用中有時(shí)候需要使用有符號(hào)數(shù)來表示一個(gè)整數(shù)，因此我們規(guī)定，當(dāng)最高位為1的時(shí)，表示為負(fù)數(shù)，最高位為0時(shí)，表示為正數(shù)2022-04-04
一般而言，每個(gè)C++/C程序通常由頭文件和定義文件組成。頭文件作為一種包含功能函數(shù)、數(shù)據(jù)接口聲明的載體文件，主要用于保存程序的聲明，而定義文件用于保存程序的實(shí)現(xiàn) 。2017-02-02
野指針和懸空指針是指針中常見的兩個(gè)概念，本文詳細(xì)的介紹了這兩種的使用，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-08-08
最近在使用中,發(fā)現(xiàn)了一種以前沒學(xué)過的using用法,于是在這里,將using的幾種用法總結(jié)一下,下面這篇文章主要給大家介紹了關(guān)于C++中using的三種用法,需要的朋友可以參考下2023-02-02
這篇文章主要為大家詳細(xì)介紹了C++vector模板類，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-03-03
C++標(biāo)準(zhǔn)模板庫函數(shù)sort的那些事兒
sort函數(shù)是標(biāo)準(zhǔn)模板庫的函數(shù)，已知開始和結(jié)束的地址即可進(jìn)行排序，可以用于比較任何容器（必須滿足隨機(jī)迭代器），任何元素，任何條件，執(zhí)行速度一般比qsort要快2013-09-09
C++實(shí)例分析組合數(shù)的計(jì)算與排列組合的產(chǎn)生
這篇文章主要介紹了C++組合數(shù)的計(jì)算與排列和組合無重集元素的產(chǎn)生，對(duì)計(jì)算算法感興趣的同學(xué)，可以參考一下，理解其原理，并且試驗(yàn)一下。2022-07-07