Hot 100 --- 最小栈

本文概览：本文讲解最小栈的核心思路：用辅助栈记录每个时刻的最小值，实现 O(1) 获取最小值

一、题目

最小栈

二、题目分析

1. 题目要求

题目要求设计一个支持以下操作的栈：

push(x)：将元素 x 推入栈中
pop()：删除栈顶元素
top()：获取栈顶元素
getMin()：获取栈中的最小元素

要求所有操作的时间复杂度都是 O(1)。

2. 难点分析

前三个操作都是栈的基本操作，直接用 Java 的 ArrayDeque 或 LinkedList 就能实现。

难点在于 getMin()。

最直觉的做法：用一个 int min 来记录最小值，每次 push 时更新 min = Math.min(min, value)。

看起来没问题：

1
2
3

push(3)  → 栈：[3]，min = 3
push(1)  → 栈：[3, 1]，min = min(3, 1) = 1
push(2)  → 栈：[3, 1, 2]，min = min(1, 2) = 1

**问题出在 pop()**：

当 pop() 删除的元素不是最小值时，min 不受影响，没问题：

1	pop() → 删除 2，栈：[3, 1]，min = 1 ✓（2 不是最小值，min 不变）

但当 pop() 删除的恰好是最小值时，min 就失效了：

1	pop() → 删除 1，栈：[3]，min = ?（1 是最小值，被删了，新的最小值是多少？）

此时 min 变量里存的还是 1，但 1 已经被弹出栈了。要找到新的最小值，只能重新遍历整个栈，时间复杂度变成 O(n)。

根本原因：一个 min 变量只能记住"当前"的最小值，但无法记住"历史"的最小值。当最小值被弹出后，我们不知道"上一个最小值"是什么——因为这个信息已经被覆盖了。

例子：

push(5)  → min = 5
push(3)  → min = 3（覆盖了 5）
push(1)  → min = 1（覆盖了 3）
pop()    → 删除 1，min = ?（3 被覆盖了，找不回来了）

所以我们需要一种方式，能够记住每一个时刻的最小值，而不是只记住当前这一个。

3. 核心思路：辅助栈

关键观察：我们需要记录每个时刻的栈的最小值，而不是只记录一个全局最小值。

解决方案：用一个辅助栈 minStack，和主栈同步操作：

push 时，往 minStack 也压入当前的最小值
pop 时，minStack 也出栈
getMin 时，直接返回 minStack 的栈顶

这样主栈的每个时刻的最小值，都和辅助栈的栈顶一一对应。

三、思路概览

class MinStack {
    private final Deque<Integer> stack;
    private final Deque<Integer> minStack;

    public MinStack() {
        stack = new LinkedList<>();
        minStack = new LinkedList<>();
    }
    
    public void push(int value) {
        stack.push(value);
        if (minStack.isEmpty()) {
            minStack.push(value);
        }
        else {
            minStack.push(Math.min(value, minStack.peek()));
        }
    }
    
    public void pop() {
        if (stack.isEmpty()) {
            return;
        }
        int top = stack.pop();
        minStack.pop();
    }
    
    public int top() {
       if (stack.isEmpty()) {
           return -1;
       }
       return stack.peek();
    }
    
    public int getMin() {
       if (minStack.isEmpty()) {
              return -1;
         }
       return minStack.peek();
    }
}

思路简要说明：

两个栈同步操作：主栈 stack 存储数据，辅助栈 minStack 存储每个时刻的最小值
push 时：minStack 压入 Math.min(value, minStack.peek())，即当前值和之前最小值的较小者
pop 时：两个栈同时出栈，保持同步
getMin 时：直接返回 minStack.peek()，O(1) 时间复杂度

四、思路详解

第一步：为什么不能用一个 int 记录最小值？

如果用一个变量 min 记录最小值：

1
2
3

push(3)  → min = 3
push(1)  → min = 1
pop()    → 删除 1，min = ?（需要遍历栈才能知道是 3）

问题：pop() 删除最小值后，无法 O(1) 获取新的最小值。

第二步：辅助栈的思路

核心思想：记录每个时刻的最小值，而不是只记录一个全局最小值。

辅助栈 minStack 的栈顶始终是当前主栈的最小值。

push 时：

1	minStack.push(Math.min(value, minStack.peek()));

如果 minStack 为空，直接压入 value
否则，压入 value 和 minStack.peek() 的较小值

pop 时：

1	minStack.pop();

两个栈同时出栈，保持同步。

getMin 时：

1	return minStack.peek();

直接返回辅助栈的栈顶，就是当前最小值。

第三步：为什么这样是对的？

关键：辅助栈的每个位置，记录的是主栈从栈底到该位置的最小值。

比如主栈是 [3, 1, 2]：

栈底是 3，此时最小值是 3
加入 1，此时最小值是 min(3, 1) = 1
加入 2，此时最小值是 min(1, 2) = 1

辅助栈就是 [3, 1, 1]，栈顶 1 就是当前最小值。

当 pop() 删除 2 时，辅助栈也出栈，变成 [3, 1]，栈顶 1 还是最小值。

当再次 pop() 删除 1 时，辅助栈也出栈，变成 [3]，栈顶 3 就是新的最小值。

完整执行过程

以 push(3), push(1), push(2), pop(), getMin(), pop(), getMin() 为例：

初始：stack = [], minStack = []

push(3)：
  stack.push(3)       → stack = [3]
  minStack 为空，压入 3 → minStack = [3]

push(1)：
  stack.push(1)       → stack = [3, 1]
  min(1, 3) = 1，压入 1 → minStack = [3, 1]

push(2)：
  stack.push(2)       → stack = [3, 1, 2]
  min(2, 1) = 1，压入 1 → minStack = [3, 1, 1]

pop()：
  stack.pop() = 2     → stack = [3, 1]
  minStack.pop() = 1  → minStack = [3, 1]

getMin()：
  return minStack.peek() = 1 ✓

pop()：
  stack.pop() = 1     → stack = [3]
  minStack.pop() = 1  → minStack = [3]

getMin()：
  return minStack.peek() = 3 ✓

再以 push(5), push(3), push(4), pop(), getMin() 为例：

初始：stack = [], minStack = []

push(5)：
  stack = [5]
  minStack = [5]

push(3)：
  stack = [5, 3]
  min(3, 5) = 3
  minStack = [5, 3]

push(4)：
  stack = [5, 3, 4]
  min(4, 3) = 3
  minStack = [5, 3, 3]

pop()：
  stack = [5, 3]
  minStack = [5, 3]

getMin()：
  return minStack.peek() = 3 ✓