最小栈

一、题目（LeetCode 155 · 中等 · Hot100）

设计支持 push、pop、top 操作，并能在常数时间 O(1) 内检索到最小元素的栈：

• MinStack() 初始化；push(val) 压栈；pop() 弹栈顶；top() 取栈顶；getMin() 获取栈中最小元素。

对 pop、top、getMin 的调用保证发生在非空栈上。

二、思路演进

2.1 朴素：getMin 时全栈扫描

数据放一个栈，getMin 每次线性扫一遍——单次 O(n)，不满足 O(1)。

2.2 第二次尝试：维护一个"当前最小"变量

min = min(min, val) 随手更新——错在 pop：弹掉的那个恰好是最小值时，"上一个最小值是多少"无从得知，单变量没有历史。

2.3 关键洞察：栈的每个状态都有自己的最小值

正确的抽象是：push 之后，栈处于某个状态 s，s 有自己的 min(s)。把这些历史最小值按同样的顺序再压一条辅助栈，两条栈永远同步：

• push：mins 压 min(val, mins 栈顶)——注意相等也压；
• pop：两栈同弹——历史最小自动"恢复"成上一层状态的值。

任意时刻 mins 栈顶就是当前栈状态的最小值，四个操作全 O(1)。这是"空间换时间 + 状态快照"的标准案例，与 有效的括号 同为栈家族。

2.4 进阶：单栈存差值

主栈不存原值，存 d = val - 入栈时的 min：d ≥ 0 表示没刷新最小值，d < 0 表示入栈时刷新了。pop 时按 d 的符号反推上一个 min——一条栈搞定，代价是要防差值溢出（val 可达 int 两端，差值用 long 存）。

三、复杂度分析

• 时间：四操作各为一次压/弹/比较，均 O(1)——推导很简单：没有任何循环。
• 空间 O(n)：辅助栈最坏与主栈等高（值单调不增的序列，每次都刷新最小）；差值版 O(n) 但系数减半。

四、代码

package org.example;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author MUYI
 * @version 1.0
 * @date 2026/10/17
 */
public class LeetCode_155 {

    public static void main(String[] args) {
        MinStack stack = new MinStack();
        stack.push(1);
        stack.push(1);
        stack.pop();                         // 弹掉一个 1，剩下的最小还是 1
        System.out.println(stack.getMin());  // 期望 1：相等元素不压辅助栈的话这里就错了
        stack.push(2);
        System.out.println(stack.top());     // 期望 2
        System.out.println(stack.getMin());  // 期望 1
    }

    /** 版本一（主推）：数据栈 + 最小值栈同步压弹 */
    static class MinStack {
        private final Deque<Integer> data = new ArrayDeque<>();
        private final Deque<Integer> mins = new ArrayDeque<>();   // 栈顶 = 当前最小

        public void push(int val) {
            data.push(val);
            // 注意是 <=：相等也必须压，否则 pop 之后最小值无法恢复
            if (mins.isEmpty() || val <= mins.peek()) {
                mins.push(val);
            }
        }

        public void pop() {
            int val = data.pop();
            if (val == mins.peek()) {        // 弹的正是当前最小，同步弹掉
                mins.pop();
            }
        }

        public int top() {
            return data.peek();
        }

        public int getMin() {
            return mins.peek();
        }
    }
    /** 版本二（进阶）：单栈存差值，min 单独维护 */
    static class DiffMinStack {
        private final Deque<Long> diffs = new ArrayDeque<>();   // x - 入栈时的 min
        private long min;

        public void push(int val) {
            if (diffs.isEmpty()) {
                min = val;
                diffs.push(0L);              // 首元素，差值 0
                return;
            }
            diffs.push((long) val - min);    // 负数 = 这次入栈刷新了最小值
            if (val < min) {
                min = val;
            }
        }

        public void pop() {
            long d = diffs.pop();
            if (d < 0) {                     // 弹的是当时的最小值，反推上一个最小
                min = min - d;
            }
        }

        public int top() {
            long d = diffs.peek();
            return d > 0 ? (int) (min + d) : (int) min;
        }

        public int getMin() {
            return (int) min;
        }
    }

}

五、坑点

• 相等元素必须压辅助栈（版本一第一坑）：push(1), push(1) 后 pop() 一次，最小值仍应是 1。若用严格 < 只压一个 1，这次 pop 会把辅助栈弹空，getMin 直接错。
• 差值版必须用 long：val 贴着 int 上下限时，val - min 会溢出 int；版本一用 int 就够，因为存的是原值。
• 差值版 pop 的恢复公式：入栈时 d = val - 上一个min 且 min 变成了 val = 上一个min + d。所以恢复是 min - d（d < 0 时相当于加回差量）；方向记反会得到更小的错误值。
• top 的分支：d > 0 时原值是 min + d；d ≤ 0 时原值就是当时的 min（现值），漏判 d == 0 会把"等于最小"的元素算错。
• 空栈约定：题目保证调用合法；工程上 pop/peek/getMin 前要判空或抛业务异常，别让 ArrayDeque 的 NPE 传出去。

六、变形追问

• 变体一（最小队列）：把同一需求搬到队列上（LeetCode 232 + 追问组合）。用"两个栈倒腾"实现队列时，最小值取两栈各自 getMin 的较小者，均摊 O(1)。考察"栈的 O(1) 最小值如何被复用"。
• 变体二（滑动窗口最大值，LeetCode 239，Hot100）：镜像问题。窗口（双端队列）内 O(1) 取最大，用单调双端队列维护"可能成为最大值的下标"。与本题主栈/辅助栈的"同步 vs 单调丢弃"是同一权衡的两面。

2026-10 新增（E 轨 · Hot100 第一批）。