單調堆疊經典問題

例題

#

給定 \(n\) 個正整數，請對於每個數字找到它左邊第一個比它小的數字 index，如果沒有則輸出 \(0\)。

\(1 \leq n \leq 10^5\)

我們幾乎可以直接套用上一章的程式碼，不過由於題目要找的是 index，所以我們可以改成在堆疊中存放 index：

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

這樣就可以在 \(O(n)\) 的時間內解決這個問題了。

原理

#

但是，到底又是為什麼這個程式碼可以正確地找到左邊第一個比它小的數字？？？讓我們來仔細解析一下單調堆疊的原理！

為了方便表示，這邊把陣列 \(a\) 中元素值的大小用高度來表示，實際的值寫在長條形中，也就是說我們的問題變成了找到每個長條形左邊第一個比它矮的長條形：

當掃到陣列的第一個項目時，因為沒有其他長條形，所以答案是 \(0\)，並且把這個長條形的 index push 進堆疊中：

堆疊中括號內的數字標示高度。

接著掃到第二個項目，因為這個長條形比堆疊中的長條形矮，所以把堆疊中的長條形 pop 出來。然後再把自己的 index push 進堆疊中：

等等，有注意到這個步驟為什麼會這麼做嗎！？因為對於之後的長方形來說，這個長方形是左邊第一個比它矮的長方形，而被我們 pop 掉那個長方形「已經不可能再被當成左邊第一個比較矮的正方形了」，因為我們已經存在另外一個「更近」又「更矮」的長方形在這裡了。這就是單調堆疊的精髓。

接著掃到第三個項目，可以發現這個步驟不需要 pop 任何長條形，然後答案就是堆疊頂端的長條形的 index（也就是第 2 個長方形），可以觀察到第 1 個長方形無論如何都不可能再被之後的長方形選到了：

持續這樣的步驟到底，我們可以在 \(O(n)\) 的時間內找到每個長條形左邊第一個比它矮的長條形了。

精簡

#

如果你仔細觀察上面的程式碼的話，其實可以發現我們在程式碼裡做了很多關於 stk.empty() 的判斷，有一個實作小技巧可以讓我們不用再做這個判斷。

只要在陣列 \(a\) 的最前面加上一個 \(0\) 的元素，因為它不可能被 pop 出來，而且在這個題目需求上剛好也是對的輸出，所以我們可以省略掉 stk.empty() 的判斷：

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

這題實際上就是 CSES - Nearest Smaller Values，你可以把這個程式碼拿去提交看看！