C++中單調棧的基本性質介紹

單調棧的定義：

單調棧就是棧內元素單調遞增或者單調遞減的棧，單調棧隻能在棧頂操作。

為瞭更好的理解單調棧，則可將單調棧用生活情形模擬實現，例如：

我們借用拿號排隊的場景來說明下。現在有很多人在排隊買可樂，每個人手裡都拿著號，越靠前的人手裡的號越小，

但是號不一定是連續的。小明拿瞭號後並沒有去排隊，而是跑去約會瞭。等他回來後，發現隊伍已經排得很長瞭，

他不能直接插入到隊伍裡，不然人傢以為他是來插隊的。小明隻能跑到隊伍最後，挨個詢問排隊人手裡的號，

小明認為號比他大的人都是“插隊”的，於是小明就會施魔法把這些人變消失，直到小明找到號比他小的為止。

在上面這個場景裡，大傢排的隊伍就像是單調棧，因為大傢手裡拿的號是單調遞增的。

而小明找自己位置的這個過程就是元素加入單調棧的過程。新加入的元素如果加到棧頂後，

如果棧裡的元素不再是單調遞增瞭，那麼我們就刪除加入前的棧頂元素，

就像小明施魔法把“插隊”的人變消失一樣。直到新元素加入後，棧依然是單調遞增時，我們才把元素加進棧裡。

（這樣做的目的是“維護”單調棧，是單調棧保持原來的單調性不變）

從數組的角度闡述單調棧的性質：

給定一個包含若幹個整數的數組，我們從第 1 個元素開始依次加入單調棧裡，並且加入後更新單調棧。

那麼單調棧有這樣的性質：對於單調遞增的棧，如果此時棧頂元素為 b，加入新元素 a 後進行更新時，

如果 a 大於 b，說明 a 在數組裡不能再往左擴展瞭（由於單調棧的單調遞增性質，b前面的元素均小於a），

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

如果 a 小於 b，說明在數組裡，a 前面至少有一個元素不能擴展到 a 的位置(至少有b元素，因為b的值要大於a，如果此時再加入新的

a，那麼單調棧便不再單調，所以元素a此時不能壓入棧頂，因為這並不是元素a”應該”在的位置，隻有當元素a找到自己的位置時

元素a方能壓入棧中，而這樣做的前提是不改變單調棧的單調性)，也就是對於這些元素來說，a 是其在數組右側第一個比它小的元素。

單調棧的維護是 O(n) 級的時間復雜度，因為所有元素隻會進入棧一次，並且出棧後再也不會進棧瞭。

單調棧的性質：

1.單調棧裡的元素具有單調性

2.元素加入棧前，會在棧頂端把破壞棧單調性的元素都刪除

3.使用單調棧可以找到元素向左遍歷第一個比他小的元素，也可以找到元素向左遍歷第一個比他大的元素。

對於第三條性質的解釋（最常用的性質）：

對於單調棧的第三條性質，你可能會產生疑問，為什麼使用單調棧可以找到元素向左遍歷第一個比他大的元素，

而不是最後一個比他大的元素呢？我們可以從單調棧中元素的單調性來解釋這個問題，由於單調棧中的元素隻能是單調遞增或者是單調

遞減的，所以我們可以分別討論這兩種情況（假設不存在兩個相同的元素）：

1.當單調棧中的元素是單調遞增的時候，根據上面我們從數組的角度闡述單調棧的性質的敘述，可以得出：

（1）.當a > b 時，則將元素a插入棧頂，新的棧頂則為a

（2）.當a < b 時，則將從當前棧頂位置向前查找（邊查找，棧頂元素邊出棧），直到找到第一個比a小的數，停止查找，將元素a

插入棧頂（在當前找到的數之後，即此時元素a找到瞭自己的“位置”）

2.當單調棧中的元素是單調遞減的時候，則有：

（1）.當a < b 時，則將元素a插入棧頂，新的棧頂則為a

（2）.當a > b 時，則將從當前棧頂位置向前查找（邊查找，棧頂元素邊出棧），直到找到第一個比a大的數，停止查找，將元素a

插入棧頂（在當前找到的數之後，即此時元素a找到瞭自己的“位置”）

到此這篇關於單調棧的基本性質介紹的文章就介紹到這瞭,更多相關單調棧的基本性質內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！