时间复杂度获取最小值)
1. 最小栈问题概述最小栈MinStack是LeetCode上经典的算法设计题编号155。这道题考察的是如何在基本栈操作的基础上增加一个能在常数时间内获取最小值的功能。作为Java开发者掌握这类数据结构的设计思想对提升编程能力至关重要。我最初接触这个问题时第一反应是用一个变量来记录最小值。但很快发现这种思路在pop操作时会遇到问题当最小值被弹出后如何快速找到次小值经过多次尝试和思考最终理解了辅助栈的设计精妙之处。2. 问题分析与解法设计2.1 问题核心难点普通栈的push、pop、top操作时间复杂度都是O(1)但获取最小值需要遍历整个栈时间复杂度为O(n)。题目要求所有操作都必须保持O(1)时间复杂度这就是主要挑战。关键观察点在于栈的LIFO后进先出特性决定了元素弹出的顺序是固定的。这意味着我们可以为每个栈状态维护一个对应的最小值。2.2 辅助栈解法详解最直观有效的解法是使用辅助栈。具体实现思路主栈xStack正常存储所有元素辅助栈minStack存储对应主栈状态下的最小值每次push操作时主栈正常压入元素辅助栈压入当前元素与辅助栈栈顶的较小值这样设计后任意时刻minStack的栈顶都是当前主栈中的最小值。public void push(int val) { xStack.push(val); minStack.push(Math.min(minStack.peek(), val)); }pop操作时两个栈同步弹出即可保持状态一致。2.3 为什么需要辅助栈很多初学者会问为什么不能只用一个变量记录最小值考虑以下操作序列push(3) → min3 push(2) → min2 push(1) → min1 pop() → 弹出1后min应该回到2单变量无法记住历史最小值而辅助栈完美解决了这个问题。3. Java实现与优化3.1 基础实现class MinStack { private DequeInteger xStack; private DequeInteger 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 实现细节解析数据结构选择使用Deque而非StackStack是遗留类性能较差ArrayDeque比LinkedList更高效基于数组实现初始化技巧minStack初始压入Integer.MAX_VALUE避免在push方法中做空栈判断边界处理虽然题目保证操作有效但实际工程中应添加空栈检查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 DequeLong 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中的记录。解决方案辅助栈法使用而非比较非同步辅助栈val minStack.peek()时压栈5.2 边界条件处理实际编码时需要考虑空栈时的pop/top/getMin操作题目保证非空但工程中需要整数溢出问题特别是差值法并发访问问题多线程环境5.3 扩展功能实现基于最小栈思想可以轻松实现其他变种最大栈MaxStack将min比较改为max中间值栈使用两个堆辅助频率栈LeetCode 895题6. 实际应用场景最小栈思想在工程中有广泛应用浏览器历史记录记录访问时间戳快速获取最早访问时间股票交易系统记录持仓成本实时获取最低买入价游戏开发角色属性buff/debuff叠加获取当前最低防御值日志监控记录请求响应时间监控最小响应时间变化7. 面试技巧与准备建议7.1 面试常见问题为什么不能用单个变量记录最小值辅助栈的空间复杂度能否优化如何处理重复最小值如何实现最大栈多线程环境下如何保证线程安全7.2 准备建议手写实现基础版和优化版画图模拟操作流程思考时间/空间复杂度权衡准备实际应用案例练习相关题目单调栈等8. 相关题目推荐LeetCode 20 - 有效的括号LeetCode 225 - 用队列实现栈LeetCode 232 - 用栈实现队列LeetCode 739 - 每日温度单调栈LeetCode 895 - 最大频率栈9. 个人实践心得在实际编码中我有几点深刻体会初始化的技巧在minStack中预先放入MAX_VALUE可以简化后续逻辑避免空栈判断。这种哨兵技巧在很多算法中都有应用。数据结构选择从Stack改为Deque虽然是小改动但体现了对Java集合框架的深入理解。面试官常会关注这些细节。测试用例设计要特别注意测试重复最小值和交替push/pop的情况。例如push(2), push(2), push(1), push(3), pop(), pop(), getMin()优化取舍虽然差值法空间更优但代码复杂度显著增加。在大多数情况下辅助栈法是更优选择除非有严格的空间限制。思维扩展掌握这个解法后可以轻松应对各种变种问题如设计同时支持min和max的栈或者设计支持O(1)时间获取平均值的栈。
