155. Min Stack

Medium

Description

設計一個支援 push、pop、top 和 getMin 的堆疊，所有操作必須在 O(1) 時間內完成。

Example:

Input: [“MinStack”,“push”,“push”,“push”,“getMin”,“pop”,“top”,“getMin”], [[],[-2],[0],[-3],[],[],[],[]] Output: [null,null,null,null,-3,null,0,-2]

Intuition#

核心思路：用一個輔助堆疊同步記錄「截至目前為止的最小值」，使 getMin 能在 O(1) 內回傳。

普通堆疊的 push/pop/top 都是 O(1)，難點在於 O(1) 取得最小值
最小值會隨著 push/pop 改變，所以需要追蹤每個「狀態」下的最小值
每次 push 時，輔助堆疊壓入 min(新值, 當前最小值)，pop 時同步彈出

Approaches#

1: 單一堆疊存 Pair#

概念: 堆疊中每個元素存 Pair(value, currentMin)，將值和對應最小值綁在一起
時間複雜度: 所有操作 O(1)
空間複雜度: O(n) - 每個元素多存一個最小值

class MinStack() {
    private val stack = ArrayDeque<Pair<Int, Int>>()

    fun push(`val`: Int) {
        val currentMin = if (stack.isEmpty()) `val` else minOf(`val`, stack.last().second)
        stack.addLast(`val` to currentMin)
    }

    fun pop() {
        stack.removeLast()
    }

    fun top(): Int {
        return stack.last().first
    }

    fun getMin(): Int {
        return stack.last().second
    }
}

⭐2: 雙堆疊（Two Stacks）#

概念: 主堆疊存數值，輔助堆疊 minStack 只在新值 <= 當前最小值時才壓入，節省空間
時間複雜度: 所有操作 O(1)
空間複雜度: O(n) - 最壞情況輔助堆疊和主堆疊一樣大，但平均更省

class MinStack() {
    private val stack = ArrayDeque<Int>()
    private val minStack = ArrayDeque<Int>()

    fun push(`val`: Int) {
        stack.addLast(`val`)
        val currentMin = if (minStack.isEmpty()) `val` else minOf(`val`, minStack.last())
        minStack.addLast(currentMin)
    }

    fun pop() {
        stack.removeLast()
        minStack.removeLast()
    }

    fun top(): Int {
        return stack.last()
    }

    fun getMin(): Int {
        return minStack.last()
    }
}

注意 minStack 必須和主堆疊同步 push/pop。如果只在「新值更小時」才 push 到 minStack 且 pop 時只在棧頂等於最小值才 pop，需要特別處理重複最小值的情況（用 <= 而非 <）。上面的實作每次都同步操作，更安全。

🔑 Takeaways#

Pattern: 需要 O(1) 追蹤額外資訊時，考慮用輔助資料結構同步維護
關鍵技巧: 輔助堆疊記錄「歷史最小值」的技巧可以推廣到追蹤最大值、頻率等場景