開發與維運

動畫:什麼是單調棧? | 算法必看系列二十七

原文鏈接

定義

小夥伴們都應該非常熟悉棧,棧的一個很鮮明的性質就是:先進後出

而所謂 單調棧 則是在棧的 先進後出 基礎之上額外添加一個特性:從棧頂到棧底的元素是嚴格遞增(or遞減)

具體進棧過程如下:

  • 對於單調遞增棧,若當前進棧元素為 e,從棧頂開始遍歷元素,把小於 e 或者等於 e 的元素彈出棧,直接遇到一個大於 e 的元素或者棧為空為止,然後再把 e 壓入棧中。
  • 對於單調遞減棧,則每次彈出的是大於 e 或者等於 e 的元素。

例子

單調遞增棧 為例進行說明。

現在有一組數

3,4,2,6,4,5,2,3

讓它們從左到右依次入棧。

具體過程如下:
image.png

作者 | 程序員小吳
來源 | 五分鐘學算法

Leave a Reply

Your email address will not be published. Required fields are marked *