單調堆疊

簡介

單調堆疊 (Monotonic Stack) 是一種特殊的堆疊，它最明顯的特性就是堆疊中的元素是單調遞增或單調遞減的。這個資料結構通常用來解決找到下一個更大或更小元素的問題。

概念

說起來容易，但在實作上該怎麼讓堆疊保持單調性呢？讓我們先以這個遞增的單調堆疊為例。

假設接下來我要把一個 $2$ push 進去，為了保持堆疊的遞增單調性，我們必須把 $4$ pop 出來：

不過這邊的 $3$ 還是會破壞單調性，所以也要 pop 掉：

這樣 $2$ 才能 push 進去：

實作方式

先來看看這份程式碼，它按照上面的邏輯實作了一個遞增的單調堆疊：

stack<int> stk;
for (int i = 1; i <= n; i++) {
    while (!stk.empty() && stk.top() >= a[i]) {
        stk.pop();
    }
    stk.push(a[i]);
}

每個元素最多只會被 push 進去一次，且最多只會被 pop 一次，所以根據 均攤分析 的概念，可以得知這個程式碼的時間複雜度是 $O(n)$。

但是你可能會想，這樣維護一個單調堆疊到底可以做什麼呢？

下一章我們將會介紹一些單調堆疊的經典問題，讓你更了解這個資料結構的威力！