时间复杂度获取最小值)
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) → 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 实现细节解析
数据结构选择：
- 使用Deque而非Stack：Stack是遗留类，性能较差
- 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 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中的记录。解决方案：
- 辅助栈法：使用<=而非<比较
- 非同步辅助栈：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)时间获取平均值的栈。
