📚 Stack

後進先出，處理括號配對、單調性與回溯。

23 題

📖 分類導讀

堆疊是後進先出 (LIFO) 的資料結構。在演算法中，堆疊常用於需要「匹配」或「追蹤最近狀態」的場景，例如括號匹配、單調堆疊等。

Notes:

  • 看到「最近的」、「匹配的」關鍵字，考慮用 Stack
  • 單調堆疊 (Monotonic Stack) 可在 O(n) 內解決「下一個更大元素」類型問題

四大應用

  • 巢狀結構匹配：括號配對、HTML 標籤閉合——遇開放符號 push，遇閉合符號 pop 並檢查是否相符。
  • 反轉順序：依序 push 再全部 pop，天然得到逆序。
  • 取代遞迴：任何遞迴都能用顯式 stack 改寫成迭代；因為遞迴的本質就是呼叫堆疊（call stack）——每層呼叫的區域狀態被層層壓入，最底層最先返回。理解這點，DFS 的遞迴版與迭代版就能互相轉換。
  • 單調堆疊：維持堆疊內元素單調遞增/遞減，O(n) 解「下一個更大/更小元素」「每日溫度」「柱狀圖最大矩形」。

所有基本操作 push / pop / peek / isEmpty 都是 O(1)。

表達式求值

用堆疊管理運算子優先級，是計算機（calculator）類題目的核心：掃描時數字進數字堆疊，運算子依優先級決定先算還是先存。基本骨架——

fun calculate(s: String): Int {
    val nums = ArrayDeque<Int>()
    var cur = 0
    var sign = '+'          // 記住「上一個」運算子
    for (i in s.indices) {
        val c = s[i]
        if (c.isDigit()) cur = cur * 10 + (c - '0')
        if ((!c.isDigit() && c != ' ') || i == s.length - 1) {
            when (sign) {
                '+' -> nums.addLast(cur)
                '-' -> nums.addLast(-cur)
                '*' -> nums.addLast(nums.removeLast() * cur)
                '/' -> nums.addLast(nums.removeLast() / cur)
            }
            sign = c
            cur = 0
        }
    }
    return nums.sum()
}

TIP

含括號的版本，可在遇到 ( 時遞迴/壓入當前狀態，遇 ) 時結算——這又回到「stack 取代遞迴」的同一個觀念。

跨倉庫導讀

#20Valid ParenthesesEasy★★★★★⏱ O(n)#22Generate ParenthesesMedium★★★★★#32Longest Valid ParenthesesHard★★★★★⏱ O(n)#71Simplify PathMedium★★★★★⏱ O(n)#84Largest Rectangle in HistogramHard★★★★★⏱ O(n)#85Maximal RectangleHard★★★★★⏱ O(m·n)#150Evaluate Reverse Polish NotationMedium★★★★★⏱ O(n)#155Min StackMedium★★★★★⏱ O(1)#225Implement Stack Using QueuesEasy★★★★★⏱ O(n)#227Basic Calculator IIMedium★★★★★⏱ O(n)#316Remove Duplicate LettersMedium★★★★★⏱ O(n)#394Decode StringMedium★★★★★⏱ O(n * maxK)#402Remove K DigitsMedium★★★★★⏱ O(n)#456132 PatternMedium★★★★★⏱ O(n)#682Baseball GameEasy★★★★★⏱ O(n)#735Asteroid CollisionMedium★★★★★⏱ O(n)#739Daily TemperaturesMedium★★★★★⏱ O(n)#853Car FleetMedium★★★★★⏱ O(n log n)#895Maximum Frequency StackHard★★★★★⏱ O(1)#901Online Stock SpanMedium★★★★★⏱ O(1)#946Validate Stack SequencesMedium★★★★★⏱ O(n)#1209Remove All Adjacent Duplicates In String IIMedium★★★★★⏱ O(n)#2390Removing Stars From a StringMedium★★★★★⏱ O(n)