每日一道 LeetCode (35)：最小栈

每天 3 分钟，走上算法的逆袭之路。

前文合集

每日一道 LeetCode 前文合集

代码仓库

GitHub： https://github.com/meteor1993/LeetCode

Gitee： https://gitee.com/inwsy/LeetCode

题目：最小栈

题目来源：https://leetcode-cn.com/problems/min-stack/

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

push(x) —— 将元素 x 推入栈中。 pop() —— 删除栈顶的元素。 top() —— 获取栈顶元素。 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.

提示：

pop、top 和 getMin 操作总是在 非空栈 上调用。

解题思路

看到这道题的第一个反应，这不就是一个数据结构栈么， Java 直接提供了啊，这还用做么？

当我把题仔细的又读了一遍以后发现，这里面有一个 getMin() 检索栈中的最小元素是 JDK 所没有提供的，那么这道题实际上就是在问，如何在栈的数据结构中检索栈中最小的元素。

经过一番仔细的思索，嗯，确认是我不会的那道题。

这就很尴尬了，打开答案看答案吧。

答案上的结果是加一个辅助栈来进行记录，记录添加到栈里最小的元素。。。

好吧，我服了，这方案确实可以。

往下翻了翻，结果还有人玩的更花，还把这个方案拆分成两种方案：同步法和不同步法。

直接一个大写的 NB 。

方案一：同步法

所谓的同步法就是在向数据栈中添加元素的时候，一起向辅助栈中也添加元素，数据栈出栈的时候辅助栈也一起出栈，辅助栈最后添加进来的数字保持最小，只有当将要进栈的数字比栈顶的数字小才能进栈，否则就将和栈顶的数字一样的数字重新进一次栈。

public class MinStack { private Stack<Integer> data; private Stack<Integer> helper; /** initialize your data structure here. */ public MinStack() { data = new Stack<> (); helper = new Stack<> (); } public void push(int x) { data.push(x); // 只有小于栈顶的数字才能进栈，否则重新将栈顶的数字进栈 if (helper.isEmpty() || helper.peek() >= x) { helper.push(x); } else { helper.push(helper.peek()); } } public void pop() { if (!data.isEmpty()) { data.pop(); helper.pop(); } } public int top() { if (!data.isEmpty()) { return data.peek(); } throw new RuntimeException("栈中元素为空，非法操作"); } public int getMin() { if(!helper.isEmpty()){ return helper.peek(); } throw new RuntimeException("栈中元素为空，此操作非法"); } }

方案二：不同步法

上面的同步法是只数据栈和辅助栈进栈出栈都是同步操作的，那么在外面的辅助栈中，能不能只存最小的值，因为它本身设计的使命就是用来查询最小值的。

public class MinStack1 { private Stack<Integer> data; private Stack<Integer> helper; /** initialize your data structure here. */ public MinStack1() { data = new Stack<> (); helper = new Stack<> (); } public void push(int x) { data.push(x); // 辅助栈只会进栈小值 if (helper.isEmpty() || helper.peek() >= x) { helper.push(x); } } public void pop() { if (!data.isEmpty()) { int top = data.pop(); // 只有当出栈的值也是小值的时候辅助栈也出栈 if(top == helper.peek()){ helper.pop(); } } } public int top() { if (!data.isEmpty()) { return data.peek(); } throw new RuntimeException("栈中元素为空，非法操作"); } public int getMin() { if(!helper.isEmpty()){ return helper.peek(); } throw new RuntimeException("栈中元素为空，此操作非法"); } }

耗时和前面的方法是一样的，只是我们所使用的辅助栈的空间变小了，但是在出栈的时候需要经过判断才能出栈。

您的扫码关注，是对小编坚持原创的最大鼓励：） 极客挖掘机 认证博客专家 Redis Java Spring 一个来自十八线城乡结合部破写代码的，平时喜欢读读书、写写代码，从2019年开始运营有自己的个人公众号：极客挖掘机，想交流的朋友可以来公众号找我聊天。