C++中單調(diào)棧的基本性質(zhì)介紹
單調(diào)棧的定義：
單調(diào)棧就是棧內(nèi)元素單調(diào)遞增或者單調(diào)遞減的棧，單調(diào)棧只能在棧頂操作。
為了更好的理解單調(diào)棧，則可將單調(diào)棧用生活情形模擬實(shí)現(xiàn)，例如：
我們借用拿號(hào)排隊(duì)的場(chǎng)景來(lái)說(shuō)明下。現(xiàn)在有很多人在排隊(duì)買(mǎi)可樂(lè)，每個(gè)人手里都拿著號(hào)，越靠前的人手里的號(hào)越小，
但是號(hào)不一定是連續(xù)的。小明拿了號(hào)后并沒(méi)有去排隊(duì)，而是跑去約會(huì)了。等他回來(lái)后，發(fā)現(xiàn)隊(duì)伍已經(jīng)排得很長(zhǎng)了，
他不能直接插入到隊(duì)伍里，不然人家以為他是來(lái)插隊(duì)的。小明只能跑到隊(duì)伍最后，挨個(gè)詢(xún)問(wèn)排隊(duì)人手里的號(hào)，
小明認(rèn)為號(hào)比他大的人都是“插隊(duì)”的，于是小明就會(huì)施魔法把這些人變消失，直到小明找到號(hào)比他小的為止。
在上面這個(gè)場(chǎng)景里，大家排的隊(duì)伍就像是單調(diào)棧，因?yàn)榇蠹沂掷锬玫奶?hào)是單調(diào)遞增的。
而小明找自己位置的這個(gè)過(guò)程就是元素加入單調(diào)棧的過(guò)程。新加入的元素如果加到棧頂后，
如果棧里的元素不再是單調(diào)遞增了，那么我們就刪除加入前的棧頂元素，
就像小明施魔法把“插隊(duì)”的人變消失一樣。直到新元素加入后，棧依然是單調(diào)遞增時(shí)，我們才把元素加進(jìn)棧里。
（這樣做的目的是“維護(hù)”單調(diào)棧，是單調(diào)棧保持原來(lái)的單調(diào)性不變）
從數(shù)組的角度闡述單調(diào)棧的性質(zhì)：
給定一個(gè)包含若干個(gè)整數(shù)的數(shù)組，我們從第 1 個(gè)元素開(kāi)始依次加入單調(diào)棧里，并且加入后更新單調(diào)棧。
那么單調(diào)棧有這樣的性質(zhì)：對(duì)于單調(diào)遞增的棧，如果此時(shí)棧頂元素為 b，加入新元素 a 后進(jìn)行更新時(shí)，
如果 a 大于 b，說(shuō)明 a 在數(shù)組里不能再往左擴(kuò)展了（由于單調(diào)棧的單調(diào)遞增性質(zhì)，b前面的元素均小于a），
也就是說(shuō)，如果從 a 在數(shù)組中的位置開(kāi)始往左邊遍歷，則 a 一定是第一個(gè)比 b 大的元素；
如果 a 小于 b，說(shuō)明在數(shù)組里，a 前面至少有一個(gè)元素不能擴(kuò)展到 a 的位置(至少有b元素，因?yàn)閎的值要大于a，如果此時(shí)再加入新的
a，那么單調(diào)棧便不再單調(diào)，所以元素a此時(shí)不能壓入棧頂，因?yàn)檫@并不是元素a"應(yīng)該"在的位置，只有當(dāng)元素a找到自己的位置時(shí)
元素a方能壓入棧中，而這樣做的前提是不改變單調(diào)棧的單調(diào)性)，也就是對(duì)于這些元素來(lái)說(shuō)，a 是其在數(shù)組右側(cè)第一個(gè)比它小的元素。
單調(diào)棧的維護(hù)是 O(n) 級(jí)的時(shí)間復(fù)雜度，因?yàn)樗性刂粫?huì)進(jìn)入棧一次，并且出棧后再也不會(huì)進(jìn)棧了。
單調(diào)棧的性質(zhì)：
1.單調(diào)棧里的元素具有單調(diào)性
2.元素加入棧前，會(huì)在棧頂端把破壞棧單調(diào)性的元素都刪除
3.使用單調(diào)棧可以找到元素向左遍歷第一個(gè)比他小的元素，也可以找到元素向左遍歷第一個(gè)比他大的元素。
對(duì)于第三條性質(zhì)的解釋?zhuān)ㄗ畛Ｓ玫男再|(zhì)）：
對(duì)于單調(diào)棧的第三條性質(zhì)，你可能會(huì)產(chǎn)生疑問(wèn)，為什么使用單調(diào)棧可以找到元素向左遍歷第一個(gè)比他大的元素，
而不是最后一個(gè)比他大的元素呢？我們可以從單調(diào)棧中元素的單調(diào)性來(lái)解釋這個(gè)問(wèn)題，由于單調(diào)棧中的元素只能是單調(diào)遞增或者是單調(diào)
遞減的，所以我們可以分別討論這兩種情況（假設(shè)不存在兩個(gè)相同的元素）：
1.當(dāng)單調(diào)棧中的元素是單調(diào)遞增的時(shí)候，根據(jù)上面我們從數(shù)組的角度闡述單調(diào)棧的性質(zhì)的敘述，可以得出：
（1）.當(dāng)a > b 時(shí)，則將元素a插入棧頂，新的棧頂則為a
（2）.當(dāng)a < b 時(shí)，則將從當(dāng)前棧頂位置向前查找（邊查找，棧頂元素邊出棧），直到找到第一個(gè)比a小的數(shù)，停止查找，將元素a
插入棧頂（在當(dāng)前找到的數(shù)之后，即此時(shí)元素a找到了自己的“位置”）
2.當(dāng)單調(diào)棧中的元素是單調(diào)遞減的時(shí)候，則有：
（1）.當(dāng)a < b 時(shí)，則將元素a插入棧頂，新的棧頂則為a
（2）.當(dāng)a > b 時(shí)，則將從當(dāng)前棧頂位置向前查找（邊查找，棧頂元素邊出棧），直到找到第一個(gè)比a大的數(shù)，停止查找，將元素a
插入棧頂（在當(dāng)前找到的數(shù)之后，即此時(shí)元素a找到了自己的“位置”）
到此這篇關(guān)于單調(diào)棧的基本性質(zhì)介紹的文章就介紹到這了,更多相關(guān)單調(diào)棧的基本性質(zhì)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
C語(yǔ)言利用UDP實(shí)現(xiàn)群聊聊天室的示例代碼
UDP是一個(gè)輕量級(jí)、不可靠、面向數(shù)據(jù)報(bào)的、無(wú)連接的傳輸層協(xié)議，多用于可靠性要求不嚴(yán)格，不是非常重要的傳輸，如直播、視頻會(huì)議等等。本文將利用UDP實(shí)現(xiàn)簡(jiǎn)單的群聊聊天室，感興趣的可以了解一下2022-08-08
這篇文章介紹了C++超集C++/CLI模塊的基本語(yǔ)法，文中通過(guò)示例代碼介紹的非常詳細(xì)。對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2022-07-07
淺談C#中List<T>對(duì)象的深度拷貝問(wèn)題
下面小編就為大家?guī)?lái)一篇淺談C#中List<T>對(duì)象的深度拷貝問(wèn)題。小編覺(jué)得挺不錯(cuò)的，現(xiàn)在就分享給大家，也給大家做個(gè)參考。一起跟隨小編過(guò)來(lái)看看吧2017-01-01
C語(yǔ)言中的浮點(diǎn)數(shù)據(jù)類(lèi)型
這篇文章主要介紹了C語(yǔ)言中的浮點(diǎn)數(shù)據(jù)類(lèi)型，文章會(huì)從處理帶小數(shù)的數(shù)值的相關(guān)資料開(kāi)始介紹,感興趣的小伙伴的可以參考下面 文章的具體內(nèi)容2021-10-10
Visual C++中Tab View的多種實(shí)現(xiàn)方法
這篇文章主要介紹了Visual C++中Tab View的多種實(shí)現(xiàn)方法,包括了CTabCtrl控件、CSheetCtrl標(biāo)簽選擇窗口以及靜態(tài)分割窗口等實(shí)現(xiàn)Tab View的方法,需要的朋友可以參考下2014-10-10
這篇文章主要介紹了C語(yǔ)言中雙鏈表的基本操作，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2023-02-02
這篇文章主要介紹了基于C語(yǔ)言自制測(cè)色弱找方塊的游戲。該游戲是仿照最近網(wǎng)上流行的找方塊游戲編寫(xiě)的，可玩性還是挺高的，感興趣的可以了解一下2022-12-12
C++從文本文件讀取數(shù)據(jù)到vector中的方法
這篇文章主要給大家介紹了利用C++如何從文本文件讀取數(shù)據(jù)到vector中，文章通過(guò)實(shí)例給出示例代碼，相信會(huì)對(duì)大家的理解和學(xué)習(xí)很有幫助，有需要的朋友們下面來(lái)一起看看吧。2016-10-10
這篇文章主要為大家詳細(xì)介紹了C/C++迭代器的失效問(wèn)題，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來(lái)幫助2022-03-03
OpenCV實(shí)現(xiàn)輪廓的發(fā)現(xiàn)
這篇文章主要為大家詳細(xì)介紹了OpenCV如何實(shí)現(xiàn)輪廓的發(fā)現(xiàn)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2019-05-05