支持 O(1) 时间获取最小值的栈

1. 简介

在本教程中，我们将介绍如何在一个栈结构中实现 push、pop、top 以及 getMin 操作，并确保所有操作的时间复杂度为 **O(1)**。

核心目标是设计一个支持常规栈操作的结构，并能在常数时间内返回当前栈中最小值。这类问题常见于高频面试题和系统设计中，尤其适合考察对数据结构的理解和优化能力。

---

2. 问题描述

设计一个数字栈，支持以下操作：

• push(x)：将元素 x 压入栈中
• pop()：移除栈顶元素
• top()：返回栈顶元素
• getMin()：返回栈中最小值

要求所有操作的时间复杂度均为 **O(1)**。

举个例子：

我们依次压入 5、6、3：

操作	栈状态	最小值
push 5	[5]	5
push 6	[5,6]	5
push 3	[5,6,3]	3
pop()	[5,6]	5

---

3. 双栈实现方案

✅ 思路

使用两个栈：

• mainStack：正常存储所有压入的元素
• minStack：辅助栈，用于记录当前栈中最小值的历史变化

每次 push 时，若当前元素小于等于 minStack 栈顶元素，则也压入 minStack；每次 pop 时，若 mainStack 和 minStack 栈顶相同，则同时弹出两个栈的栈顶。

⚠️ 注意点

• minStack 的栈顶始终保存当前栈中最小值
• mainStack 和 minStack 必须保持同步，否则 getMin() 会出错

✅ 示例图示

步骤	mainStack	minStack
push 5	[5]	[5]
push 6	[5,6]	[5]
push 3	[5,6,3]	[5,3]
pop()	[5,6]	[5]

✅ Java 实现代码

class MinStack {
    private Stack<Integer> mainStack = new Stack<>();
    private Stack<Integer> minStack = new Stack<>();

    public void push(int val) {
        mainStack.push(val);
        if (minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val);
        }
    }

    public void pop() {
        if (mainStack.pop().equals(minStack.peek())) {
            minStack.pop();
        }
    }

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

    public int getMin() {
        return minStack.peek();
    }
}

✅ 时间复杂度分析

方法	时间复杂度
push	O(1)
pop	O(1)
top	O(1)
getMin	O(1)

❌ 缺点

• 额外使用了一个栈，空间复杂度为 O(n)
• 对于大量重复最小值的情况，minStack 会占用较多空间

---

4. 单栈 + 数学优化实现方案

✅ 思路

使用一个栈和一个变量 minValue 来记录当前最小值。在压栈时通过数学公式进行变换，使得当最小值变化时，栈中存储的是一个“标记值”，用于在弹栈时恢复前一个最小值。

✅ 核心公式

当压入的值 val < minValue 时：

stack.push(2 * val - minValue);
minValue = val;

当弹出的值小于 minValue 时（说明这是一个最小值标记）：

minValue = 2 * poppedValue - minValue;

⚠️ 注意点

• 栈中存储的不一定是原始值，尤其是最小值变化时
• 恢复最小值依赖于弹出的值和当前 minValue 的计算
• 该方法适用于所有整数（包括负数）

✅ 示例图示

步骤	mainStack	minValue
push 5	[5]	5
push 6	[5,6]	5
push 3	[5,6,1]	3
pop()	[5,6]	5

注：1 是通过 2 * 3 - 5 计算而来，用于标记最小值变化

✅ Java 实现代码

class MinStack {
    private Stack<Long> stack = new Stack<>();
    private long minValue;

    public MinStack() {
        minValue = Long.MAX_VALUE;
    }

    public void push(int val) {
        if (stack.isEmpty()) {
            stack.push((long) val);
            minValue = val;
        } else if (val < minValue) {
            stack.push(2L * val - minValue);
            minValue = val;
        } else {
            stack.push((long) val);
        }
    }

    public void pop() {
        long top = stack.pop();
        if (top < minValue) {
            minValue = 2 * minValue - top;
        }
    }

    public int top() {
        long top = stack.peek();
        if (top < minValue) {
            return (int) minValue;
        } else {
            return (int) top;
        }
    }

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

✅ 时间复杂度分析

方法	时间复杂度
push	O(1)
pop	O(1)
top	O(1)
getMin	O(1)

✅ 空间复杂度分析

方法	空间复杂度
使用栈	O(n)
最小值变量	O(1)

✅ 优点

• 仅使用一个栈，空间占用更少
• 无需额外栈来记录最小值历史
• 适用于负数和重复最小值场景

⚠️ 缺点

• 实现逻辑较复杂，需要数学推导
• 不适合直接用于浮点数（需要额外处理）

---

5. 总结与选择建议

方案	是否使用辅助栈	空间复杂度	适用场景	推荐程度
双栈实现	✅ 是	O(n)	逻辑清晰，适合面试	⭐⭐⭐⭐
单栈 + 数学	❌ 否	O(1)	空间敏感，性能要求高	⭐⭐⭐

✅ 推荐使用场景

• 双栈方案：适合对代码可读性要求高、面试或教学场景
• 单栈方案：适合嵌入式环境、内存受限、追求极致性能的系统

⚠️ 踩坑提醒

• minStack 和 mainStack 必须同步，否则 getMin() 会出错
• Long 类型用于避免整数溢出问题
• 使用 Long.MAX_VALUE 初始化 minValue 避免边界错误

---