PHP 實現 O(1) 時間複雜度的 Min Stack：面試經典題深度解析

題目背景

面試高頻題：使用兩個棧實現一個特殊棧，要求 push、pop、min 三個操作的時間複雜度均為 O(1)，其中 min() 返回當前棧中的最小值。

思路演進：從誤區到正解

❌ 失敗嘗試 1：單變量記錄最小值

用一個變量 $minVal 保存當前最小值。push 時比較更新，min 直接返回。但 pop 彈出最小值時，需重新掃描整棧找新最小值，複雜度退化為 O(n)。

❌ 失敗嘗試 2：有序輔助棧

輔助棧維護遞增序列。min 取棧頂即可，但 push/pop 需插入/刪除排序位置，無法達到 O(1)。

✅ 正解：同步記錄「歷史最小值」

核心洞察：輔助棧不存「所有元素排序」，而是存「每一步操作後的當前最小值」。

• Push：新元素與輔助棧頂比較，較小者入輔助棧。
• Pop：數據棧、輔助棧同步彈出。
• Min：直接返回輔助棧頂元素。

這樣三個操作均為單次棧頂訪問，嚴格 O(1)。

PHP 完整實現

top === -1) {
            $this->data[] = $element;
            $this->minStack[] = $element;
            $this->top++;
            return true;
        }
        // 關鍵：比較新元素與當前最小值，取較小者入輔助棧
        $currentMin = min($element, $this->minStack[$this->top]);
        $this->data[] = $element;
        $this->minStack[] = $currentMin;
        $this->top++;
        return true;
    }

    /** 出棧 */
    public function pop(): int|bool {
        if ($this->top === -1) return false;
        array_pop($this->minStack);
        $this->top--;
        return array_pop($this->data);
    }

    /** 獲取最小值 */
    public function min(): int|bool {
        if ($this->top === -1) return false;
        return $this->minStack[$this->top];
    }
}

// 測試用例
$stack = new MinStack();
$stack->push(12);
$stack->push(56);
$stack->push(23);
$stack->push(89);
$stack->push(4);
var_dump($stack->min()); // int(4)
$stack->pop();
var_dump($stack->min()); // int(12)
$stack->push(8);
var_dump($stack->min()); // int(8)

圖解執行過程

複雜度與空間分析

• 時間：push/pop/min 均為 O(1)
• 空間：O(n) 額外空間（輔助棧與數據棧等長）
• 適用場景：高頻調用 min() 的實時系統、算法競賽、嵌入式受限環境

擴展思考

1. 若需支持 max()，同理再加一個 maxStack。
2. 若記憶體極度敏感，可優化輔助棧：僅在最小值發生變化時壓入 (value, count) 元組，節省空間。
3. C++ STL 中可用 std::stack 配合 std::vector 實現同樣邏輯。

這道題考察的不僅是棧的特性，更是「以空間換時間」及「狀態歷史記錄」的通用設計模式，值得深度體會。