單調(diào)棧的定義：

單調(diào)棧就是棧內(nèi)元素單調(diào)遞增或者單調(diào)遞減的棧，單調(diào)棧只能在棧頂操作。

為了更好的理解單調(diào)棧，則可將單調(diào)棧用生活情形模擬實(shí)現(xiàn)，例如：

我們借用拿號(hào)排隊(duì)的場(chǎng)景來說明下。現(xiàn)在有很多人在排隊(duì)買可樂，每個(gè)人手里都拿著號(hào)，越靠前的人手里的號(hào)越小，

但是號(hào)不一定是連續(xù)的。小明拿了號(hào)后并沒有去排隊(duì)，而是跑去約會(huì)了。等他回來后，發(fā)現(xiàn)隊(duì)伍已經(jīng)排得很長(zhǎng)了，

他不能直接插入到隊(duì)伍里，不然人家以為他是來插隊(duì)的。小明只能跑到隊(duì)伍最后，挨個(gè)詢問排隊(duì)人手里的號(hào)，

小明認(rèn)為號(hào)比他大的人都是“插隊(duì)”的，于是小明就會(huì)施魔法把這些人變消失，直到小明找到號(hào)比他小的為止。

在上面這個(gè)場(chǎng)景里，大家排的隊(duì)伍就像是單調(diào)棧，因?yàn)榇蠹沂掷锬玫奶?hào)是單調(diào)遞增的。

而小明找自己位置的這個(gè)過程就是元素加入單調(diào)棧的過程。新加入的元素如果加到棧頂后，

如果棧里的元素不再是單調(diào)遞增了，那么我們就刪除加入前的棧頂元素，

就像小明施魔法把“插隊(duì)”的人變消失一樣。直到新元素加入后，棧依然是單調(diào)遞增時(shí)，我們才把元素加進(jìn)棧里。

（這樣做的目的是“維護(hù)”單調(diào)棧，是單調(diào)棧保持原來的單調(diào)性不變）

從數(shù)組的角度闡述單調(diào)棧的性質(zhì)：

給定一個(gè)包含若干個(gè)整數(shù)的數(shù)組，我們從第 1 個(gè)元素開始依次加入單調(diào)棧里，并且加入后更新單調(diào)棧。

那么單調(diào)棧有這樣的性質(zhì)：對(duì)于單調(diào)遞增的棧，如果此時(shí)棧頂元素為 b，加入新元素 a 后進(jìn)行更新時(shí)，

如果 a 大于 b，說明 a 在數(shù)組里不能再往左擴(kuò)展了（由于單調(diào)棧的單調(diào)遞增性質(zhì)，b前面的元素均小于a），

也就是說，如果從 a 在數(shù)組中的位置開始往左邊遍歷，則 a 一定是第一個(gè)比 b 大的元素；

如果 a 小于 b，說明在數(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ì)于這些元素來說，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ì)的解釋（最常用的性質(zhì)）：

對(duì)于單調(diào)棧的第三條性質(zhì)，你可能會(huì)產(chǎn)生疑問，為什么使用單調(diào)?？梢哉业皆叵蜃蟊闅v第一個(gè)比他大的元素，

而不是最后一個(gè)比他大的元素呢？我們可以從單調(diào)棧中元素的單調(diào)性來解釋這個(gè)問題，由于單調(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)文章希望大家以后多多支持腳本之家！

最新評(píng)論