單調棧

引入

何為單調棧？顧名思義，單調棧即滿足單調性的棧結構。與單調隊列相比，其只在一端進行進出。

為了描述方便，以下舉例及偽代碼以維護一個整數的單調遞增棧為例。

過程

插入

將一個元素插入單調棧時，為了維護棧的單調性，需要在保證將該元素插入到棧頂後整個棧滿足單調性的前提下彈出最少的元素。

例如，棧中自頂向下的元素為 \(\{0,11,45,81\}\)。

插入元素 \(14\) 時為了保證單調性需要依次彈出元素 \(0,11\)，操作後棧變為 \(\{14,45,81\}\)。

用偽代碼描述如下：

實現

insert x
while !sta.empty() && sta.top()<x
    sta.pop()
sta.push(x)

使用

自然就是從棧頂讀出來一個元素，該元素滿足單調性的某一端。

例如舉例中取出的即棧中的最小值。

應用

POJ3250 Bad Hair Day

有 \(N\) 頭牛從左到右排成一排，每頭牛有一個高度 \(h_i\)，設左數第 \(i\) 頭牛與「它右邊第一頭高度 \(≥h_i\)」的牛之間有 \(c_i\) 頭牛，試求 \(\sum_{i=1}^{N} c_i\)。

比較基礎的應用有這一題，就是個單調棧的簡單應用，記錄每頭牛被彈出的位置，如果沒有被彈出過則為最遠端，稍微處理一下即可計算出題目所需結果。

另外，單調棧也可以用於離線解決 RMQ 問題。

我們可以把所有詢問按右端點排序，然後每次在序列上從左往右掃描到當前詢問的右端點處，並把掃描到的元素插入到單調棧中。這樣，每次回答詢問時，單調棧中存儲的值都是位置 \(\le r\) 的、可能成為答案的決策點，並且這些元素滿足單調性質。此時，單調棧上第一個位置 \(\ge l\) 的元素就是當前詢問的答案，這個過程可以用二分查找實現。使用單調棧解決 RMQ 問題的時間複雜度為 \(O(q\log q + q\log n)\)，空間複雜度為 \(O(n)\)。

習題

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用