宣城市网站建设_网站建设公司_一站式建站_seo优化

Java版LeetCode热题100之最小栈：深入解析与实战应用

本文将全面剖析 LeetCode 热题第155题《最小栈》，从题目理解、算法设计、代码实现，到复杂度分析、面试技巧、实际应用场景，层层递进，帮助你彻底掌握这一经典数据结构问题。

一、原题回顾

题目描述：

设计一个支持push、pop、top操作，并能在常数时间内检索到最小元素的栈。

实现MinStack类：

• MinStack()初始化堆栈对象。
• void push(int val)将元素val推入堆栈。
• void pop()删除堆栈顶部的元素。
• int top()获取堆栈顶部的元素。
• int getMin()获取堆栈中的最小元素。

示例：

输入： ["MinStack","push","push","push","getMin","pop","top","getMin"] [[],[-2],[0],[-3],[],[],[],[]] 输出： [null,null,null,null,-3,null,0,-2] 解释： MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.getMin(); --> 返回 -2.

约束条件：

• -2^31 <= val <= 2^31 - 1
• pop、top和getMin操作总是在非空栈上调用
• 所有操作最多被调用3 * 10^4次

二、原题分析

2.1 核心需求

本题的核心挑战在于：如何在 O(1) 时间内获取当前栈中的最小值？

我们知道，普通栈（Stack）天然支持push、pop、top操作，且时间复杂度均为 O(1)。但若要获取最小值，常规做法是遍历整个栈，时间复杂度为 O(n)，这显然不符合题目要求。

因此，我们需要一种辅助机制，使得在每次操作后，都能立即知道当前栈中的最小值，而无需重新计算。

2.2 关键观察

栈的“先进后出”特性决定了：一旦某个元素 a 入栈，只要 a 还在栈中，它下面的所有元素就一定还在栈中。

这意味着：每个栈状态（即从栈底到当前栈顶的元素序列）是确定且唯一的。

因此，我们可以为每一个栈状态维护一个对应的最小值。当执行push或pop时，同步更新这个“最小值记录”。

三、答案构思

3.1 思路一：辅助栈（推荐）

使用两个栈：

• 主栈（xStack）：存储所有入栈的元素。
• 辅助栈（minStack）：与主栈同步操作，存储对应状态下栈中的最小值。

同步策略：

• push(x)：
  • 主栈压入 x；
  • 辅助栈压入min(当前辅助栈顶, x)。
• pop()：
  • 主栈弹出；
  • 辅助栈同步弹出。
• getMin()：
  • 直接返回辅助栈顶。

初始时，可将Integer.MAX_VALUE压入辅助栈，避免空栈判断。

3.2 思路二：单栈 + 差值编码（进阶）

（本文重点讲解思路一，思路二将在“优化思路”部分简要介绍）

该方法仅用一个栈，通过存储“当前值与最小值的差值”来隐式维护最小值，节省空间。但逻辑较复杂，易出错，面试中不推荐优先使用。

四、完整答案（Java实现）

importjava.util.Deque;importjava.util.LinkedList;classMinStack{// 主栈：存储实际元素privateDeque<Integer>xStack;// 辅助栈：存储每个状态下的最小值privateDeque<Integer>minStack;/** 初始化 */publicMinStack(){xStack=newLinkedList<>();minStack=newLinkedList<>();// 初始最小值设为最大整数，便于后续比较minStack.push(Integer.MAX_VALUE);}/** 入栈 */publicvoidpush(intval){xStack.push(val);// 当前最小值 = min(之前的最小值, 当前值)minStack.push(Math.min(minStack.peek(),val));}/** 出栈 */publicvoidpop(){if(!xStack.isEmpty()){xStack.pop();minStack.pop();}}/** 获取栈顶元素 */publicinttop(){returnxStack.peek();}/** 获取最小元素 */publicintgetMin(){returnminStack.peek();}}

说明：虽然题目保证pop、top、getMin在非空栈上调用，但为代码健壮性，pop()中仍加了空栈判断（实际可省略）。

五、代码分析

5.1 数据结构选择

• 使用Deque<Integer>而非Stack<Integer>：
  • Stack是遗留类，线程安全但性能较差；
  • Deque（双端队列）作为栈使用更高效，且是 Java 官方推荐方式（见《Effective Java》）。

5.2 初始化细节

minStack.push(Integer.MAX_VALUE);

• 此举确保第一次push时，Math.min(minStack.peek(), val)能正确返回val；
• 避免在push中判断minStack.isEmpty()，简化逻辑。

5.3 同步操作

• push和pop操作严格同步两个栈；
• 保证任意时刻，minStack的大小与xStack相同；
• minStack的第 i 个元素表示：当主栈有 i 个元素时的最小值。

5.4 示例执行过程

以输入[-2, 0, -3]为例：

注意：栈顶在左，符合Deque.push()行为（插入头部）。

六、时间复杂度与空间复杂度分析

6.1 时间复杂度

• push()：O(1) —— 两次栈操作（主栈+辅助栈）
• pop()：O(1) —— 两次栈弹出
• top()：O(1) —— 主栈 peek
• getMin()：O(1) —— 辅助栈 peek

✅所有操作均为常数时间，满足题目要求。

6.2 空间复杂度

• 主栈：O(n)
• 辅助栈：O(n)
• 总计：O(n)，其中 n 为入栈元素个数。

最坏情况下（如单调递减序列），辅助栈每个元素都不同，空间开销最大。

七、常见问题解答（FAQ）

Q1：为什么不用一个变量记录最小值？

答：因为pop()可能弹出当前最小值，此时需要知道次小值。单变量无法回溯历史最小值。

Q2：辅助栈是否冗余？能否优化空间？

答：可以！见下文“优化思路”中的“非同步辅助栈”或“差值法”。

Q3：如果允许重复最小值，会影响结果吗？

答：不会。例如[2, 1, 1]，辅助栈为[MAX, 2, 1, 1]，pop两次后仍能正确返回2。

Q4：为什么初始化minStack为MAX_VALUE？

答：确保第一次push时Math.min(MAX, val) == val，逻辑统一。也可在push中判断空栈，但代码更啰嗦。

八、优化思路

8.1 优化1：非同步辅助栈（节省空间）

思想：只有当新元素 ≤ 当前最小值时，才将其压入辅助栈。

publicvoidpush(intval){xStack.push(val);if(val<=minStack.peek()){// 注意：用 <=，处理重复最小值minStack.push(val);}}publicvoidpop(){intval=xStack.pop();if(val==minStack.peek()){minStack.pop();}}

优点：

• 空间最坏仍 O(n)，但平均情况更优（如递增序列，辅助栈仅存第一个元素）。

缺点：

• 需要额外比较和判断；
• 处理重复最小值时必须用<=，否则pop会漏删。

8.2 优化2：单栈 + 差值编码（极致空间优化）

核心思想：

• 只维护一个栈和一个全局min变量；
• 栈中存储的是val - min（差值）；
• 当val < min时，更新min = val，并压入val - oldMin（负数）；
• 弹出时，若栈顶为负数，说明曾更新过min，需还原。

classMinStack{privateDeque<Long>stack;privatelongmin;publicMinStack(){stack=newLinkedList<>();min=Long.MAX_VALUE;}publicvoidpush(intval){if(stack.isEmpty()){min=val;stack.push(0L);}else{longdiff=(long)val-min;stack.push(diff);if(diff<0){min=val;// 更新最小值}}}publicvoidpop(){longdiff=stack.pop();if(diff<0){min=min-diff;// 还原上一个 min}}publicinttop(){longdiff=stack.peek();if(diff<0){return(int)min;}else{return(int)(min+diff);}}publicintgetMin(){return(int)min;}}

优点：

• 空间 O(n) 但只用一个栈；
• 无额外辅助栈。

缺点：

• 逻辑复杂，易出错；
• 需处理整数溢出（故用long）；
• 面试中不推荐，除非明确要求空间优化。

✅结论：辅助栈法是最清晰、最易理解、最不易出错的解法，应作为首选。

九、数据结构与算法基础知识点回顾

9.1 栈（Stack）

• 定义：后进先出（LIFO）的线性数据结构。
• 基本操作：
  • push(x)：入栈
  • pop()：出栈
  • peek()/top()：查看栈顶
  • isEmpty()：判空
• 应用场景：函数调用栈、表达式求值、括号匹配、DFS 等。

9.2 辅助数据结构思想

• 核心：用额外空间换取时间效率。
• 典型应用：
  • 最小栈（本题）
  • 单调栈（求下一个更大元素）
  • 哈希表加速查找（如两数之和）
  • 前缀和/积数组（区间查询）

9.3 时间 vs 空间权衡（Time-Space Tradeoff）

• 本题是经典案例：用 O(n) 额外空间，将 O(n) 查询优化为 O(1)。
• 工程中需根据场景权衡：内存充足？查询频繁？等。

十、面试官提问环节（模拟）

Q1：你的解法空间复杂度是 O(n)，有没有办法降低？

答：有的。可以采用“非同步辅助栈”，只在新元素 ≤ 当前最小值时才压入辅助栈。这样在数据单调递增时，辅助栈大小仅为 1，平均空间更优。另外还有“单栈差值法”，但逻辑复杂，一般不推荐。

Q2：如果栈支持max()操作，怎么做？

答：完全对称！只需将minStack改为maxStack，Math.min改为Math.max即可。

Q3：如果要求同时支持getMin()和getMax()呢？

答：使用两个辅助栈：minStack和maxStack，分别维护最小值和最大值，同步操作即可。

Q4：你的代码中用了LinkedList实现栈，为什么不用ArrayDeque？

答：ArrayDeque更高效（基于循环数组，缓存友好），确实是更好的选择。我这里用LinkedList是为了强调“栈”的抽象，实际工程中推荐ArrayDeque。

✅ 改进版：

xStack=newArrayDeque<>();minStack=newArrayDeque<>();

Q5：如果入栈元素是对象（如 Student），如何实现最小栈？

答：要求对象实现Comparable接口，或传入Comparator。辅助栈存储逻辑不变，比较时调用compareTo或compare方法。

十一、这道算法题在实际开发中的应用

11.1 浏览器历史记录（带最小访问时间）

• 每次访问网页，记录 URL 和时间戳；
• 需快速获取“最早访问的页面”（即时间戳最小）；
• 可用最小栈维护时间戳。

11.2 股票交易系统（实时最低价）

• 用户下单时，系统需知道当前持仓成本的最低买入价；
• 每次买入压栈，卖出弹栈；
• getMin()返回最低成本，用于盈亏计算。

11.3 日志监控（最小响应时间）

• Web 服务器记录每次请求的响应时间；
• 用最小栈维护最近 N 次请求的最小响应时间；
• 用于性能告警（如最小响应时间突增，可能系统异常）。

11.4 游戏开发（角色属性栈）

• 角色装备可叠加 buff/debuff；
• 某些属性（如防御力）取栈中最小值（最弱环节）；
• 装备穿戴/卸下对应push/pop，getMin()获取当前防御。

💡本质：任何需要“撤销操作”且需维护历史极值”的场景，都可用最小栈思想。

十二、相关题目推荐

🔔建议：掌握最小栈后，可挑战“最大频率栈”（LeetCode 895），进一步巩固辅助数据结构思想。

十三、总结与延伸

13.1 核心总结

• 最小栈问题是栈的经典变种，考察对数据结构特性的理解；
• 辅助栈法是最优解：思路清晰、代码简洁、效率高；
• 关键在于利用栈的状态确定性，为每个状态预存最小值；
• 时间 O(1)，空间 O(n)，符合题目所有要求。

13.2 延伸思考

• 泛化：能否设计“第 k 小栈”？（提示：用平衡 BST 或堆维护，但pop难以 O(1)）
• 持久化：能否支持“回到历史版本的最小值”？（需持久化数据结构）
• 并发安全：多线程环境下如何保证MinStack线程安全？（加锁 or 无锁栈）

13.3 学习建议

1. 手写代码：务必独立实现辅助栈版本；
2. 画图理解：用纸笔模拟push/pop过程；
3. 对比优化：尝试实现非同步辅助栈和差值法；
4. 举一反三：思考如何实现“最大栈”、“平均栈”等变种。

🌟最后寄语：算法题不仅是面试敲门砖，更是培养工程思维的利器。最小栈虽小，却蕴含“空间换时间”、“状态同步”、“数据结构组合”等重要思想。掌握它，你就离优秀工程师更近一步！