LeetCode 155：最小棧的設計與實現（雙棧法與向量法）

題目描述

設計一個支持 push、pop、top 操作，並能在常數時間內檢索最小元素的棧。

解題思路

使用兩個棧：一個存儲所有元素（allStack），另一個存儲歷史最小值（minStack）。壓入新元素時，若其小於等於當前最小值，則同時壓入 minStack；彈出時，若彈出元素等於 minStack 栈頂，則同步彈出 minStack。這樣 getMin() 直接返回 minStack 栈頂即可。

雙棧實現 (C++)

class MinStack {
public:
    stack<int> allStack;
    stack<int> minStack;

    void push(int x) {
        allStack.push(x);
        if (minStack.empty() || x <= minStack.top()) {
            minStack.push(x);
        }
    }

    void pop() {
        if (allStack.top() == minStack.top()) {
            minStack.pop();
        }
        allStack.pop();
    }

    int top() {
        return allStack.top();
    }

    int getMin() {
        return minStack.top();
    }
};

向量實現 (C++)

同樣邏輯，使用 vector 模擬棧操作。但實測效率略低於標準庫 stack。

class MinStack {
public:
    vector<int> allVec;
    vector<int> minVec;

    void push(int x) {
        allVec.push_back(x);
        if (minVec.empty() || x <= minVec.back()) {
            minVec.push_back(x);
        }
    }

    void pop() {
        if (allVec.back() == minVec.back()) {
            minVec.pop_back();
        }
        allVec.pop_back();
    }

    int top() {
        return allVec.back();
    }

    int getMin() {
        return minVec.back();
    }
};

總結

雙棧法是標準解法，時間複雜度均為 O(1)，空間複雜度 O(n)。向量版本雖然邏輯相同，但因動態擴容機制導致常數因子較大。