定義
小夥伴們都應該非常熟悉棧,棧的一個很鮮明的性質就是:先進後出 。
而所謂 單調棧 則是在棧的 先進後出 基礎之上額外添加一個特性:從棧頂到棧底的元素是嚴格遞增(or遞減)。
具體進棧過程如下:
- 對於單調遞增棧,若當前進棧元素為
e
,從棧頂開始遍歷元素,把小於e
或者等於e
的元素彈出棧,直接遇到一個大於e
的元素或者棧為空為止,然後再把e
壓入棧中。 - 對於單調遞減棧,則每次彈出的是大於
e
或者等於e
的元素。
例子
以 單調遞增棧 為例進行說明。
現在有一組數
3,4,2,6,4,5,2,3
讓它們從左到右依次入棧。
具體過程如下:
作者 | 程序員小吳
來源 | 五分鐘學算法