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