1. 首页
  2. LeetCode

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

每日一道 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 直接提供了啊,这还用做么?

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

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

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

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

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

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

直接一个大写的 NB 。

## 方案一:同步法

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

```java
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("栈中元素为空,此操作非法");
    }
}

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

方案二:不同步法

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

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("栈中元素为空,此操作非法");
    }
}

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

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

转载声明:本博客由极客挖掘机创作,采用 CC BY 3.0 CN 许可协议。可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在文末添加作者公众号二维码。

发表评论

电子邮件地址不会被公开。 必填项已用*标注

QR code