Java实现最小栈：O(1)时间复杂度获取最小值

发布时间：2026/11/4 8:05:06
Java实现最小栈：O(1)时间复杂度获取最小值

1. 最小栈问题概述

最小栈（MinStack）是LeetCode上经典的算法设计题，编号155。这道题考察的是如何在基本栈操作的基础上，增加一个能在常数时间内获取最小值的功能。作为Java开发者，掌握这类数据结构的设计思想对提升编程能力至关重要。

我最初接触这个问题时，第一反应是用一个变量来记录最小值。但很快发现这种思路在pop操作时会遇到问题：当最小值被弹出后，如何快速找到次小值？经过多次尝试和思考，最终理解了辅助栈的设计精妙之处。

2. 问题分析与解法设计

2.1 问题核心难点

普通栈的push、pop、top操作时间复杂度都是O(1)，但获取最小值需要遍历整个栈，时间复杂度为O(n)。题目要求所有操作都必须保持O(1)时间复杂度，这就是主要挑战。

关键观察点在于：栈的LIFO（后进先出）特性决定了元素弹出的顺序是固定的。这意味着我们可以为每个栈状态维护一个对应的最小值。

2.2 辅助栈解法详解

最直观有效的解法是使用辅助栈。具体实现思路：

  1. 主栈（xStack）：正常存储所有元素
  2. 辅助栈（minStack）：存储对应主栈状态下的最小值

每次push操作时：

  • 主栈正常压入元素
  • 辅助栈压入当前元素与辅助栈栈顶的较小值

这样设计后，任意时刻minStack的栈顶都是当前主栈中的最小值。

public void push(int val) { xStack.push(val); minStack.push(Math.min(minStack.peek(), val)); }

pop操作时，两个栈同步弹出即可保持状态一致。

2.3 为什么需要辅助栈

很多初学者会问：为什么不能只用一个变量记录最小值？考虑以下操作序列：

push(3) → min=3 push(2) → min=2 push(1) → min=1 pop() → 弹出1后，min应该回到2

单变量无法记住历史最小值，而辅助栈完美解决了这个问题。

3. Java实现与优化

3.1 基础实现

class MinStack { private Deque<Integer> xStack; private Deque<Integer> minStack; public MinStack() { xStack = new ArrayDeque<>(); minStack = new ArrayDeque<>(); minStack.push(Integer.MAX_VALUE); } public void push(int val) { xStack.push(val); minStack.push(Math.min(minStack.peek(), val)); } public void pop() { xStack.pop(); minStack.pop(); } public int top() { return xStack.peek(); } public int getMin() { return minStack.peek(); } }

3.2 实现细节解析

  1. 数据结构选择：

    • 使用Deque而非Stack：Stack是遗留类，性能较差
    • ArrayDeque比LinkedList更高效（基于数组实现）

  2. 初始化技巧：

    • minStack初始压入Integer.MAX_VALUE
    • 避免在push方法中做空栈判断

  3. 边界处理：

    • 虽然题目保证操作有效，但实际工程中应添加空栈检查

3.3 时间复杂度分析

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

  • push：两次push操作
  • pop：两次pop操作
  • top：一次peek操作
  • getMin：一次peek操作

空间复杂度O(n)，最坏情况下需要额外n空间存储最小值。

4. 优化方案探讨

4.1 非同步辅助栈优化

当数据量大时，可以考虑优化辅助栈的空间使用：

public void push(int val) { xStack.push(val); if (val <= minStack.peek()) { minStack.push(val); } } public void pop() { int val = xStack.pop(); if (val == minStack.peek()) { minStack.pop(); } }

这种实现下：

  • 空间复杂度最坏仍是O(n)
  • 但对于递增序列，辅助栈只存储一个元素
  • 需要注意处理重复最小值的情况（使用<=而非<）

4.2 差值编码法（进阶）

更极致的空间优化是使用单栈+差值编码：

class MinStack { private Deque<Long> stack; private long min; public void push(int val) { if (stack.isEmpty()) { min = val; stack.push(0L); } else { long diff = (long) val - min; stack.push(diff); if (diff < 0) min = val; } } public void pop() { long diff = stack.pop(); if (diff < 0) min = min - diff; } public int top() { long diff = stack.peek(); if (diff < 0) return (int) min; return (int) (min + diff); } public int getMin() { return (int) min; } }

这种方法：

  • 只使用一个栈，存储元素与当前min的差值
  • 当差值<0时，表示min被更新
  • 需要处理整数溢出问题（使用long）
  • 代码复杂度高，面试时不建议优先使用

5. 常见问题与解决方案

5.1 处理重复最小值

当栈中存在多个相同的最小值时，必须确保pop操作不会过早移除minStack中的记录。解决方案：

  1. 辅助栈法：使用<=而非<比较
  2. 非同步辅助栈：val <= minStack.peek()时压栈

5.2 边界条件处理

实际编码时需要考虑：

  • 空栈时的pop/top/getMin操作（题目保证非空，但工程中需要）
  • 整数溢出问题（特别是差值法）
  • 并发访问问题（多线程环境）

5.3 扩展功能实现

基于最小栈思想，可以轻松实现其他变种：

  • 最大栈（MaxStack）：将min比较改为max
  • 中间值栈：使用两个堆辅助
  • 频率栈：LeetCode 895题

6. 实际应用场景

最小栈思想在工程中有广泛应用：

  1. 浏览器历史记录：

    • 记录访问时间戳
    • 快速获取最早访问时间

  2. 股票交易系统：

    • 记录持仓成本
    • 实时获取最低买入价

  3. 游戏开发：

    • 角色属性buff/debuff叠加
    • 获取当前最低防御值

  4. 日志监控：

    • 记录请求响应时间
    • 监控最小响应时间变化

7. 面试技巧与准备建议

7.1 面试常见问题

  1. 为什么不能用单个变量记录最小值？
  2. 辅助栈的空间复杂度能否优化？
  3. 如何处理重复最小值？
  4. 如何实现最大栈？
  5. 多线程环境下如何保证线程安全？

7.2 准备建议

  1. 手写实现基础版和优化版
  2. 画图模拟操作流程
  3. 思考时间/空间复杂度权衡
  4. 准备实际应用案例
  5. 练习相关题目（单调栈等）

8. 相关题目推荐

  1. LeetCode 20 - 有效的括号
  2. LeetCode 225 - 用队列实现栈
  3. LeetCode 232 - 用栈实现队列
  4. LeetCode 739 - 每日温度（单调栈）
  5. LeetCode 895 - 最大频率栈

9. 个人实践心得

在实际编码中，我有几点深刻体会：

  1. 初始化的技巧：在minStack中预先放入MAX_VALUE，可以简化后续逻辑，避免空栈判断。这种"哨兵"技巧在很多算法中都有应用。

  2. 数据结构选择：从Stack改为Deque，虽然是小改动，但体现了对Java集合框架的深入理解。面试官常会关注这些细节。

  3. 测试用例设计：要特别注意测试重复最小值和交替push/pop的情况。例如：

    push(2), push(2), push(1), push(3), pop(), pop(), getMin()

  4. 优化取舍：虽然差值法空间更优，但代码复杂度显著增加。在大多数情况下，辅助栈法是更优选择，除非有严格的空间限制。

  5. 思维扩展：掌握这个解法后，可以轻松应对各种变种问题，如设计同时支持min和max的栈，或者设计支持O(1)时间获取平均值的栈。