155. 最小栈

难度：🟡 Medium | 标签：栈、设计 | 状态：⬜ LeetCode 链接

思路

辅助栈同步存「截至当前的最小值」。 push 时压 min(新值, 当前栈顶 min)；pop 时两栈同步弹。

代码

class MinStack {
    stack<int> s, m;
public:
    void push(int x) {
        s.push(x);
        m.push(m.empty() ? x : min(x, m.top()));
    }
    void pop() { s.pop(); m.pop(); }
    int top() { return s.top(); }
    int getMin() { return m.top(); }
};

复杂度

• 全部操作 O(1)
• 空间 O(n)

易错 / 回顾

• 辅助栈高度始终与主栈相同
• 单栈解法存差值，省一半空间但易错
• pop 必须同步弹辅助栈