如何设计一个能在 O(1) 时间获取最小值的栈（最小栈）？

简化版

用辅助栈：主栈正常存所有元素，另一个「最小栈」的栈顶始终是当前主栈里的最小值。每次入栈时，往最小栈压入 min(新值, 当前最小)；出栈时两个栈一起弹。这样 getMin() 直接读最小栈的栈顶，O(1)。push、pop、top、getMin 全部 O(1)。

详细版

要求栈的 push / pop / top / getMin 都是 O(1)。难点在 getMin：普通栈取最小要遍历 O(n)。用一个和主栈同步涨落的辅助栈记录「每一层的最小值」：

class MinStack {
    private Deque<Integer> stack = new ArrayDeque<>();   // 主栈
    private Deque<Integer> min   = new ArrayDeque<>();   // 最小栈，栈顶=当前最小

    public void push(int x) {
        stack.push(x);
        // 压入「x 和当前最小 中的较小者」
        min.push(min.isEmpty() ? x : Math.min(x, min.peek()));
    }
    public void pop()      { stack.pop(); min.pop(); }   // 同步弹出
    public int top()       { return stack.peek(); }
    public int getMin()    { return min.peek(); }        // O(1)
}

关键：最小栈第 i 层存的是「主栈前 i 个元素的最小值」，所以它的栈顶永远是当前整个栈的最小值，且随主栈同步出入，始终对得上。

完整版教学

一、为什么普通栈取最小是 O(n)

普通栈只知道栈顶，要找最小值得把所有元素扫一遍，O(n)。如果每次 getMin 都遍历，频繁调用就很慢。目标是用额外空间换时间，把最小值「预先记好」，做到 O(1) 查询。

二、辅助栈法：核心不变式

维护第二个栈 min，保证一个不变式：min 的栈顶 = 主栈当前所有元素的最小值。怎么维持？

push(x)：新的最小值只可能是「x」或「原来的最小值」，取较小者压入 min。于是 min 和主栈层数一致，每一层都记录了「到这一层为止的最小值」。
pop()：主栈弹一个，min 也弹一个，两栈层数始终相等，min 栈顶自动回退到「弹之前那一层的最小值」，依旧正确。

因为两栈严格同步涨落，min 栈顶永远对应「当前主栈的最小值」。

三、走一遍验证

push 3 → stack:[3]      min:[3]
push 5 → stack:[3,5]    min:[3]        (min(5,3)=3)
push 2 → stack:[3,5,2]  min:[3,3,2]    (min(2,3)=2)  getMin=2 ✓
pop    → stack:[3,5]    min:[3,3]      getMin=3 ✓（自动回退）
push 1 → stack:[3,5,1]  min:[3,3,1]    getMin=1 ✓

弹出 2 之后，最小值自动恢复成 3，正是因为 min 栈同步弹出了那一层。

四、优化：只在最小值变化时才记

上面 min 栈和主栈一样高，空间 O(n)。可以优化：只有当新值 ≤ 当前最小时才压入 min，pop 时只有当弹出的值等于 min 栈顶时才弹 min。这样 min 栈只记录「最小值发生变化的节点」，重复的大值不占空间：

public void push(int x) {
    stack.push(x);
    if (min.isEmpty() || x <= min.peek()) min.push(x);
}
public void pop() {
    int x = stack.pop();
    if (x == min.peek()) min.pop();   // 注意用 <= 入栈，相等也入，才能安全这样弹
}

入栈条件必须是 <=（相等也压）。否则有重复最小值时，pop 一次就把唯一的最小记录弹掉了，导致后续 getMin 出错。这是最容易踩的坑。

五、不用辅助栈的做法（进阶）

也可以只用一个栈，存「差值」：压入 x - 当前最小，并用一个变量记当前最小值。栈顶为负说明来了更小的值，据此还原。空间 O(1)（不算主栈），但逻辑绕、易出错，且有溢出风险。面试首选辅助栈法，清晰稳妥。

六、常见误区与追问

操作	数据栈	辅助最小栈	不变量
push(x)	压入 x	压入当前最小值	min 栈顶始终是全局最小
pop()	弹出栈顶	同步弹出或按规则弹出	两栈状态对应
getMin()	不扫描	直接读 min 栈顶	O(1)

易错点：MinStack 的关键不是“保存出现过的最小值”，而是让每个栈状态都能 O(1) 知道当前最小值。

数字例子：依次 push 3, 5, 2, 2, 4。若辅助栈每次同步记录当前最小值，它会是 3, 3, 2, 2, 2；连续 pop 掉 4、2 后，辅助栈顶仍能准确回到 2；再 pop 一个 2，最小值回到 3。重复最小值必须处理好，否则弹出一个 2 后可能错误地认为最小值已经变成 3。

误区：只用一个变量记录最小值就够了。 当最小值被弹出时，需要知道上一个最小值，单变量无法恢复历史状态。
误区：辅助栈只在 x < min 时入栈。 如果有重复最小值，通常要在 x <= min 时记录，或在同步辅助栈中每次记录当前最小。
误区：getMin 可以临时遍历数据栈。 题目要求 O(1)，遍历会退化到 O(n)。
追问：两种辅助栈写法怎么选？ 同步记录当前最小值代码最简单但空间多；只记录变化点更省空间但要处理重复值。
追问：pop 时为什么 min 栈也要更新？ 弹出数据会改变当前栈状态，最小值必须回到弹出前一个状态。
追问：不用辅助栈能不能做？ 可以用差值编码等进阶技巧，但可读性和溢出边界更复杂，面试标准答案仍是辅助栈。

七、加强记忆

最小栈用辅助栈：主栈存数据，最小栈栈顶始终是当前最小值——push 时压入 min(x, 当前最小)、pop 时两栈同步弹，getMin 直接读栈顶，全 O(1)。省空间版只在「新值 ≤ 当前最小」时压最小栈、弹出值等于最小栈顶时才弹它，入栈条件必须用 <=（否则重复最小值会出错）。

简化版

详细版