获取最小值的算法精解)
1. 最小栈问题概述
最小栈（Min Stack）是LeetCode上经典的算法设计题（#155题），要求设计一个栈数据结构，除了支持常规的push、pop、top操作外，还能在常数时间内检索到栈中的最小元素。这个问题看似简单，却蕴含着数据结构设计的精妙思想，也是面试中检验候选人基础功底的常见题型。
在实际工程中，类似最小栈的设计思想被广泛应用于需要快速获取极值的场景，比如实时监控系统中的最小值报警、交易系统中的历史最低价追踪等。理解这个问题的解法，不仅能帮助通过算法面试，更能培养出优化数据结构的思维模式。
2. 问题分析与解法思路
2.1 问题核心要求
最小栈问题的核心难点在于：如何在保证栈的基本操作时间复杂度为O(1)的前提下，同时实现getMin()操作的O(1)时间复杂度。常规的栈结构虽然push/pop/top都是O(1)，但获取最小值需要遍历整个栈，时间复杂度为O(n)。
2.2 辅助栈解法原理
最经典的解法是使用辅助栈（Min Stack）：
- 主栈：正常存储所有元素
- 辅助栈：栈顶始终存储当前主栈中的最小值
每次push操作时：
- 主栈正常push
- 比较新元素与辅助栈栈顶元素
- 将较小者push到辅助栈
这样辅助栈的栈顶永远保存着当前主栈的最小值，getMin()只需返回辅助栈栈顶即可。
2.3 单栈解法优化
更节省空间的解法是只使用一个栈，但每个节点额外存储当前最小值：
class MinStack { private static class Node { int val; int min; Node(int val, int min) { this.val = val; this.min = min; } } private Stack<Node> stack; public MinStack() { stack = new Stack<>(); } public void push(int val) { int min = stack.isEmpty() ? val : Math.min(val, stack.peek().min); stack.push(new Node(val, min)); } // 其他方法... }这种方法虽然节省了一个栈的空间，但每个节点需要额外存储min值，空间复杂度与辅助栈解法相同（都是O(n)）。
3. Java实现与代码解析
3.1 完整实现代码
import java.util.Stack; class MinStack { private Stack<Integer> mainStack; private Stack<Integer> minStack; public MinStack() { mainStack = new Stack<>(); minStack = new Stack<>(); } public void push(int val) { mainStack.push(val); if (minStack.isEmpty() || val <= minStack.peek()) { minStack.push(val); } else { minStack.push(minStack.peek()); } } public void pop() { if (!mainStack.isEmpty()) { mainStack.pop(); minStack.pop(); } } public int top() { return mainStack.peek(); } public int getMin() { return minStack.peek(); } }3.2 关键操作解析
push操作：
- 主栈无条件push
- 辅助栈push当前最小值（新值与栈顶较小者）
- 时间复杂度：O(1)
pop操作：
- 主栈和辅助栈同步pop
- 不需要额外比较
- 时间复杂度：O(1)
getMin操作：
- 直接返回辅助栈栈顶
- 时间复杂度：O(1)
3.3 边界条件处理
- 空栈pop/top/getMin：实际代码中应抛出异常，但LeetCode题目保证操作有效
- 相等最小值处理：当新值等于当前最小值时，仍需push到辅助栈，否则pop时可能丢失最小值
4. 复杂度分析与优化
4.1 时间复杂度
所有操作（push/pop/top/getMin）都是O(1)，满足题目要求。
4.2 空间复杂度
最坏情况下需要额外O(n)空间存储最小值信息：
- 辅助栈解法：最坏情况下每个主栈元素都对应一个辅助栈元素
- 单栈解法：每个节点存储额外min值
4.3 空间优化方案
当存在大量连续相同最小值时，可以优化辅助栈存储：
public void push(int val) { mainStack.push(val); if (minStack.isEmpty() || val <= minStack.peek().val) { minStack.push(new Pair(val, 1)); } else if (val == minStack.peek().val) { minStack.peek().count++; } } public void pop() { if (mainStack.pop() == minStack.peek().val) { if (minStack.peek().count == 1) { minStack.pop(); } else { minStack.peek().count--; } } }这种优化在存在大量重复最小值时可以显著减少辅助栈空间使用。
5. 实际应用场景
5.1 系统监控报警
在实时监控系统中，需要快速获取最近一段时间内的最小值（如CPU使用率最低值）：
class SystemMonitor { private MinStack minStack = new MinStack(); private long windowStart; private final long windowSize; public void addMetric(int value) { if (System.currentTimeMillis() - windowStart > windowSize) { // 滑动窗口逻辑 } minStack.push(value); } public int getMinInWindow() { return minStack.getMin(); } }5.2 股票交易系统
追踪股票历史价格中的最低点：
class StockPriceTracker { private MinStack priceStack = new MinStack(); public void addPrice(int price) { priceStack.push(price); } public int getHistoricalLow() { return priceStack.getMin(); } }5.3 游戏得分系统
在游戏中记录玩家得分并快速获取当前最低分：
class GameScoreSystem { private MinStack scoreStack = new MinStack(); public void addScore(int score) { scoreStack.push(score); } public int getCurrentMinScore() { return scoreStack.getMin(); } }6. 常见问题与解决方案
6.1 为什么辅助栈要存储重复最小值？
考虑序列：3 → 1 → 1
- 第一次push 1：辅助栈 3 → 1
- 第二次push 1：如果不存储，辅助栈 3 → 1
- pop第一个1后，辅助栈只剩3，但实际最小值仍是1
因此当新值等于当前最小值时，仍需push到辅助栈。
6.2 如何处理大量数据时的内存问题？
对于数据量特别大的场景：
- 使用更紧凑的数据结构（如数组实现的栈）
- 采用滑动窗口模式，定期清理过期数据
- 考虑使用概率数据结构（如HyperLogLog）近似计算极值
6.3 多线程环境下的线程安全问题
标准实现不是线程安全的，多线程环境下需要：
class ConcurrentMinStack { private final Stack<Integer> mainStack = new Stack<>(); private final Stack<Integer> minStack = new Stack<>(); private final Object lock = new Object(); public void push(int val) { synchronized(lock) { mainStack.push(val); minStack.push(minStack.isEmpty() ? val : Math.min(val, minStack.peek())); } } // 其他方法也需同步... }7. 变种问题与扩展思考
7.1 最大栈问题
同样的思路可以实现O(1)获取最大值的MaxStack，只需修改辅助栈的比较逻辑。
7.2 中间值栈问题
如果要实现O(1)获取中位数，则需要更复杂的数据结构（如两个堆）。
7.3 最小队列问题
实现一个队列，支持O(1)获取最小值，可以使用双端队列辅助：
class MinQueue { private Deque<Integer> mainQueue; private Deque<Integer> minQueue; public void enqueue(int val) { mainQueue.addLast(val); while (!minQueue.isEmpty() && minQueue.getLast() > val) { minQueue.removeLast(); } minQueue.addLast(val); } public int dequeue() { if (mainQueue.getFirst().equals(minQueue.getFirst())) { minQueue.removeFirst(); } return mainQueue.removeFirst(); } public int getMin() { return minQueue.getFirst(); } }7.4 带失效时间的极值统计
在实际系统中，经常需要统计最近N分钟内的极值，这需要结合最小栈和滑动窗口算法。
8. 测试用例设计与验证
8.1 基础测试用例
@Test public void testBasicOperations() { MinStack stack = new MinStack(); stack.push(-2); stack.push(0); stack.push(-3); assertEquals(-3, stack.getMin()); // 最小值-3 stack.pop(); assertEquals(0, stack.top()); // 栈顶0 assertEquals(-2, stack.getMin()); // 最小值-2 }8.2 边界测试用例
@Test public void testEdgeCases() { MinStack stack = new MinStack(); stack.push(Integer.MAX_VALUE); stack.push(Integer.MIN_VALUE); assertEquals(Integer.MIN_VALUE, stack.getMin()); stack.pop(); assertEquals(Integer.MAX_VALUE, stack.getMin()); stack.push(5); stack.push(5); stack.pop(); assertEquals(5, stack.getMin()); // 重复最小值测试 }8.3 性能测试
@Test public void testPerformance() { MinStack stack = new MinStack(); long start = System.nanoTime(); for (int i = 0; i < 1000000; i++) { stack.push(i); stack.push(-i); stack.getMin(); } long duration = System.nanoTime() - start; assertTrue(duration < 1000000000); // 1秒内完成百万次操作 }9. 工程实践中的注意事项
API设计：
- 考虑添加isEmpty()方法
- pop/top/getMin在空栈时应抛出明确异常
- 考虑泛型支持（Comparable）
内存管理：
- 对于Java实现，注意栈扩容带来的性能影响
- 考虑设置初始容量减少扩容次数
日志与监控：
- 在生产环境中添加操作日志
- 监控getMin的调用频率
序列化支持：
- 如果需要持久化，实现Serializable接口
- 考虑自定义序列化格式减少空间占用
10. 与其他数据结构的比较
10.1 最小栈 vs 最小堆
| 特性 | 最小栈 | 最小堆 |
|---|---|---|
| 获取最小值 | O(1) | O(1) |
| 插入 | O(1) | O(log n) |
| 删除 | O(1) | O(log n) |
| 空间复杂度 | O(n) | O(n) |
| 适用场景 | 需要LIFO顺序+最小值 | 只需要频繁获取最小值 |
10.2 最小栈 vs 单调栈
单调栈是另一种常用数据结构，用于解决"下一个更大元素"类问题：
- 单调栈维护栈内元素的单调性
- 最小栈可以看作是一种特殊的单调栈（单调递减）
11. 历史题目演变与面试趋势
最小栈问题自LeetCode早期就已存在，近年来出现了一些变种：
- 最大栈（#716）
- 队列中的最大值（剑指Offer 59-II）
- 带失效时间的极值统计（系统设计题）
在面试中，这个问题常常作为热身题出现，后续可能追问：
- 如何优化空间复杂度？
- 如何处理数据流中的极值？
- 如何设计支持O(1)获取中位数的数据结构？
12. 个人实现心得
在实际实现最小栈时，有几个容易忽略的细节：
相等值的处理：当新值等于当前最小值时，必须将其push到辅助栈，否则后续pop会导致最小值丢失。
Integer缓存问题：Java中Integer缓存-128到127，比较时应用equals而非==：
// 错误写法 if (val == minStack.peek()) {...} // 正确写法 if (val.equals(minStack.peek())) {...}初始状态处理：空栈时调用getMin()应明确抛出异常而非返回默认值。
空间优化取舍：虽然可以优化辅助栈的空间，但会增加代码复杂度，在一般场景下标准实现已经足够。
测试覆盖率：特别注意测试重复值、边界值(Integer.MAX_VALUE/MIN_VALUE)和交替push/pop的序列。
