最小栈 图解题解

这道题真正在问什么

设计一个栈，除了常规的 push、pop、top，还要提供 getMin——在常数时间内返回栈中当前的最小元素。难点全在「常数时间」四个字：栈里的内容随压弹不断变化，最小值也跟着变，getMin 却不许现场遍历去找。这是一道考「用空间换时间、为查询预留答案」的设计题。

为什么一个最小值变量不够用

最直觉的偷懒办法是维护一个变量 min，push 时顺手更新。压栈没问题，坏在 pop：一旦弹出的恰好是当前最小值，min 该回退成「剩下元素里的最小值」——可这个值是多少，单个变量没有记录，只能重新遍历整个栈去找，O(1) 就破功了。

这暴露了问题的真正需求：我们需要的不是「一个最小值」，而是「每个历史时刻的最小值」，弹栈时才能随时回退到上一个状态。历史状态要跟着栈的压弹同步存取——后压的状态先失效——这本身又是一个后进先出的过程，所以答案呼之欲出：再用一个栈来存最小值的历史。

辅助栈的不变量怎么定义

开一个辅助栈 mn，与主栈 st 保持两条不变量：一是高度永远相等，二是 mn 的第 i 层存「主栈从栈底到第 i 层这一段的最小值」。于是 mn 的栈顶恒等于当前整个主栈的最小值，getMin 读一下栈顶就完事。

维护也只要两条同步规则。push(x) 时：主栈压 x，辅助栈压 min(x, mn 栈顶)——新最小值要么是 x 自己，要么延续原来的最小值；辅助栈为空时直接压 x。pop 时：两栈同时弹一个。注意辅助栈压的是取 min 之后的结果而不是 x 本身，压 x 本身的话栈顶就不再代表全栈最小，整个设计就塌了。

为什么 pop 之后最小值自动恢复正确

关键在于辅助栈每一层的含义是「截至这一层的前缀最小值」，它只由主栈更低的那些层决定，与后来压入的元素无关。弹掉栈顶后，露出来的新栈顶记录的正是「剩余那些元素的最小值」——这个答案在当初压栈时就算好存在那里了，弹栈只是把它重新露出来，不需要任何补算。

这就是本题的核心思想：与其在查询时现找答案，不如在每次入栈时把「此刻的答案」一并存档，出栈时档案随之销毁，任何时刻栈顶档案都与栈内容严格对应。

复杂度怎么算，有哪些进阶变体

四个操作 push、pop、top、getMin 都只做常数次栈操作，时间各是 O(1)；辅助栈与主栈一样高，额外空间 O(n)。

空间上有两个常见优化方向：一是辅助栈只在新元素小于等于栈顶时才压入，弹栈时判断相等才同步弹，能省掉大量重复的最小值，但相等情形的处理容易写错；二是「差值法」，主栈存 x 与当前最小值的差、外加一个 min 变量，能把额外空间压到 O(1)，代价是要处理编码解码和数值溢出。面试先把基础辅助栈讲清楚，再提这两个变体作为亮点即可。

Python

class MinStack:
    def __init__(self):
        self.st = []          # 主栈
        self.mn = []          # 辅助栈：同步存最小值
    def push(self, x: int) -> None:
        self.st.append(x)
        m = x if not self.mn else min(x, self.mn[-1])
        self.mn.append(m)     # 压入 min(x, 辅助栈顶)
    def pop(self) -> None:
        self.st.pop()
        self.mn.pop()         # 两栈同步弹
    def top(self) -> int:
        return self.st[-1]
    def getMin(self) -> int:
        return self.mn[-1]    # O(1)：辅助栈顶即最小值

C++

class MinStack {
    stack<int> st, mn;        // 主栈 + 辅助栈
public:
    void push(int x) {
        st.push(x);
        mn.push(mn.empty() ? x : min(x, mn.top()));
    }
    void pop() { st.pop(); mn.pop(); }   // 同步弹
    int top() { return st.top(); }
    int getMin() { return mn.top(); }    // O(1)
};

Java

class MinStack {
    private Deque<Integer> st = new ArrayDeque<>(); // 主栈
    private Deque<Integer> mn = new ArrayDeque<>(); // 辅助栈
    public void push(int x) {
        st.push(x);
        mn.push(mn.isEmpty() ? x : Math.min(x, mn.peek()));
    }
    public void pop() { st.pop(); mn.pop(); }   // 同步弹
    public int top() { return st.peek(); }
    public int getMin() { return mn.peek(); }   // O(1)
}