C++ 實現帶 GetMin 的棧 - O(1) 時間取最小值

題目要求

實現一個棧，支持 push、pop、getMin 三種操作，全部 O(1) 時間。

核心思想：輔助最小棧

主棧存數據，輔助棧 minStack 同步存儲「當前主棧中的最小值」。

• push(x)：主棧壓入 x；若 minStack 為空或 x <= minStack.top()，則 minStack 也壓入 x。（用 <= 保證重複最小值正確計數）
• pop()：主棧彈出；若彈出值等於 minStack.top()，則 minStack 也彈出。
• getMin()：直接返回 minStack.top()。

模板實現 (C++)

#include 
#include 
#include 
using namespace std;

template 
class MinStack {
public:
    void push(const T& x) {
        _data.push(x);
        if (_minStack.empty() || x <= _minStack.top())
            _minStack.push(x);
    }

    void pop() {
        if (_data.empty()) throw underflow_error("stack empty");
        if (_data.top() == _minStack.top())
            _minStack.pop();
        _data.pop();
    }

    const T& top() const {
        if (_data.empty()) throw underflow_error("stack empty");
        return _data.top();
    }

    const T& getMin() const {
        if (_minStack.empty()) throw underflow_error("stack empty");
        return _minStack.top();
    }

    bool empty() const { return _data.empty(); }
    size_t size() const { return _data.size(); }

private:
    stack _data;
    stack _minStack;
};

// 測試
int main() {
    MinStack s;
    s.push(3); s.push(5); s.push(2); s.push(2); s.push(1);
    cout << "Min: " << s.getMin() << endl; // 1
    s.pop(); // 彈出 1
    cout << "Min: " << s.getMin() << endl; // 2
    s.pop(); // 彈出 2
    cout << "Min: " << s.getMin() << endl; // 2 (還有一個 2)
    s.pop(); // 彈出 2
    cout << "Min: " << s.getMin() << endl; // 3
    return 0;
}

變體：單棧編碼法（節省空間）

不額外開棧，而是將「與當前最小值的差值」壓入主棧。當新值 x < minVal 時，壓入 x - minVal（負數），並更新 minVal = x。出棧時若棧頂 < 0，說明該元素曾是最小值，恢復 minVal = minVal - top。此法僅需一個變量額外空間，但涉及溢出風險，適合整數類型。

複雜度

• 所有操作：O(1) 時間
• 空間：O(n) 雙棧（或 O(1) 單棧編碼）

總結

「輔助棧同步最小值」是面試標準答案，邏輯清晰、易擴展（如同時支持 getMax）。模板寫法體現泛型編程能力。注意 push 判斷用 <= 以正確處理重複最小值。