【五分钟学算法面试现场】如何实现可以获取最小值的栈?


小史是一个应届生,虽然学的是电子专业,但是自己业余时间看了很多互联网与编程方面的书,一心想进BAT。


【五分钟学算法面试现场】如何实现可以获取最小值的栈?


今天他又去BAT中的一家面试了。


简单的自我介绍后,面试官给了小史一个问题。


【五分钟学算法面试现场】


【五分钟学算法面试现场】如何实现可以获取最小值的栈?



【五分钟学算法面试现场】如何实现可以获取最小值的栈?


题目:我现在需要实现一个栈,这个栈除了可以进行普通的pushpop操作以外,还可以进行getMin的操作,getMin方法被调用后,会返回当前栈的最小值,你会怎么做呢?你可以假设栈里面存的都是int整数。



【五分钟学算法面试现场】如何实现可以获取最小值的栈?


【五分钟学算法面试现场】如何实现可以获取最小值的栈?


【五分钟学算法面试现场】如何实现可以获取最小值的栈?


【五分钟学算法面试现场】如何实现可以获取最小值的栈?


【五分钟学算法面试现场】如何实现可以获取最小值的栈?

【五分钟学算法面试现场】如何实现可以获取最小值的栈?

【五分钟学算法面试现场】如何实现可以获取最小值的栈?

【五分钟学算法面试现场】如何实现可以获取最小值的栈?

【五分钟学算法面试现场】如何实现可以获取最小值的栈?


【五分钟学算法面试现场】如何实现可以获取最小值的栈?


【五分钟学算法面试现场】如何实现可以获取最小值的栈?


【五分钟学算法面试现场】如何实现可以获取最小值的栈?

【五分钟学算法面试现场】如何实现可以获取最小值的栈?

【五分钟学算法面试现场】如何实现可以获取最小值的栈?



【五分钟学算法面试现场】如何实现可以获取最小值的栈?


【五分钟学算法面试现场】如何实现可以获取最小值的栈?


【五分钟学算法面试现场】如何实现可以获取最小值的栈?


【五分钟学算法面试现场】如何实现可以获取最小值的栈?


【五分钟学算法面试现场】如何实现可以获取最小值的栈?


【五分钟学算法面试现场】如何实现可以获取最小值的栈?

【五分钟学算法面试现场】如何实现可以获取最小值的栈?


小史熟练地把代码写了出来。


import java.util.ArrayList;
import java.util.List;

/**
 * @author xiaoshi on 2018/9/1.
 */

public class MinStack {

    private List<Integer> data = new ArrayList<Integer>();
    private List<Integer> mins = new ArrayList<Integer>();

    public void push(int num) {
        data.add(num);
        if(mins.size() == 0) {
            // 初始化mins
            mins.add(num);
        } else {
            // 辅助栈mins每次push当时最小值
            int min = getMin();
            if (num >= min) {
                mins.add(min);
            } else {
                mins.add(num);
            }
        }
    }

    public int pop() {
        // 栈空,异常,返回-1
        if(data.size() == 0) {
            return -1;
        }
        // pop时两栈同步pop
        mins.remove(mins.size() - 1);
        return data.remove(data.size() - 1);
    }

    public int getMin() {
        // 栈空,异常,返回-1
        if(mins.size() == 0) {
            return -1;
        }
        // 返回mins栈顶元素
        return mins.get(mins.size() - 1);
    }

}


【五分钟学算法面试现场】如何实现可以获取最小值的栈?


【五分钟学算法面试现场】如何实现可以获取最小值的栈?


【五分钟学算法面试现场】如何实现可以获取最小值的栈?

【五分钟学算法面试现场】如何实现可以获取最小值的栈?


【请教大神】


小史回到学校,把面试的情况和计算机学院的吕老师说了一下。


【五分钟学算法面试现场】如何实现可以获取最小值的栈?


【五分钟学算法面试现场】如何实现可以获取最小值的栈?


【五分钟学算法面试现场】如何实现可以获取最小值的栈?


【五分钟学算法面试现场】如何实现可以获取最小值的栈?


【五分钟学算法面试现场】如何实现可以获取最小值的栈?


【异常情况处理】


【五分钟学算法面试现场】如何实现可以获取最小值的栈?

吕老师:面试官已经提出了你的异常处理有点问题,当栈内为空的时候,你返回-1,但是如果用户push-1,那么你返回-1的时候,是用户push进来的值,还是栈为空,就不得而知了。


【五分钟学算法面试现场】如何实现可以获取最小值的栈?


【五分钟学算法面试现场】如何实现可以获取最小值的栈?

【五分钟学算法面试现场】如何实现可以获取最小值的栈?

小史咬咬牙:那就再定义一个类,里面包括一个intdata和一个booleanisSuccess,正常情况下isSuccesstrue,栈为空的话,isSuccessfalse。这样就能区分开了吧?


【五分钟学算法面试现场】如何实现可以获取最小值的栈?


【五分钟学算法面试现场】如何实现可以获取最小值的栈?


小史突然一拍大腿:对哦,我可以用一个包装类Integer来定义返回值,如果是空,就代表栈为空就行了。它和int的区别就是它多了一个null,正好用来返回异常情况。


【五分钟学算法面试现场】如何实现可以获取最小值的栈?


吕老师:嗯,越来越好,但是还是有点问题。你并没有站在使用者的角度考虑问题。使用你这个栈的人,在pop的时候,他并不知道可能返回null,如果他不做判断,后面的代码就可能抛出空指针了。


【五分钟学算法面试现场】如何实现可以获取最小值的栈?


【五分钟学算法面试现场】如何实现可以获取最小值的栈?


【五分钟学算法面试现场】如何实现可以获取最小值的栈?


【五分钟学算法面试现场】如何实现可以获取最小值的栈?


吕老师发来一个表情。


【五分钟学算法面试现场】如何实现可以获取最小值的栈?


【五分钟学算法面试现场】如何实现可以获取最小值的栈?


【五分钟学算法面试现场】如何实现可以获取最小值的栈?

【五分钟学算法面试现场】如何实现可以获取最小值的栈?

吕老师:没错,最关键的是,你显式抛出异常,如果使用者不捕获,那么编译就会报错,这样就把错误暴露在编译阶段,并且不需要和任何人商量所谓的特殊返回值了


【五分钟学算法面试现场】如何实现可以获取最小值的栈?


【五分钟学算法面试现场】如何实现可以获取最小值的栈?


【算法优化】


【五分钟学算法面试现场】如何实现可以获取最小值的栈?


【五分钟学算法面试现场】如何实现可以获取最小值的栈?


吕老师一眼看穿了小史的心思。

【五分钟学算法面试现场】如何实现可以获取最小值的栈?


【五分钟学算法面试现场】如何实现可以获取最小值的栈?

【五分钟学算法面试现场】如何实现可以获取最小值的栈?

【五分钟学算法面试现场】如何实现可以获取最小值的栈?

【五分钟学算法面试现场】如何实现可以获取最小值的栈?

小史想了想:明白了,我可以在push的时候判断一下,如果比最小值还大,就不加入辅助栈。pop的时候,如果不是最小值,辅助栈就不出栈。这样一来,辅助栈就不会有大量重复元素了。


【五分钟学算法面试现场】如何实现可以获取最小值的栈?

小史:push的时候进行判断,如果数值比当前最小值大,就不动mins栈了,这样mins栈中不会保存大量冗余的最小值。pop的时候同样进行判断,只有pop出的数就是当前最小值的时候,才让mins出栈。


【五分钟学算法面试现场】如何实现可以获取最小值的栈?


【五分钟学算法面试现场】如何实现可以获取最小值的栈?

【五分钟学算法面试现场】如何实现可以获取最小值的栈?

小史:如果push一个和最小值相等的元素,还是要入mins栈。不然当这个最小值pop出去的时候。data中还会有一个最小值元素,而mins中却已经没有最小值元素了。

【五分钟学算法面试现场】如何实现可以获取最小值的栈?


【五分钟学算法面试现场】如何实现可以获取最小值的栈?


【五分钟学算法面试现场】如何实现可以获取最小值的栈?


【五分钟学算法面试现场】如何实现可以获取最小值的栈?

【五分钟学算法面试现场】如何实现可以获取最小值的栈?

小史:mins栈中改存最小值在data数组中的索引。这样一来,当push了与最小值相同元素的时候,就不需要动mins栈了。而pop的时候,pop出的元素的索引如果不是mins栈顶元素,mins也不出栈。同时,获取最小值的时候,需要拿到mins栈顶元素作为索引,再去data数组中找到相应的数作为最小值。

【五分钟学算法面试现场】如何实现可以获取最小值的栈?

【五分钟学算法面试现场】如何实现可以获取最小值的栈?

理解了算法之后,小史的代码写起来也是非常快,不一会儿就写好了:


import java.util.ArrayList;
import java.util.List;

/**
 * @author xiaoshi on 2018/9/1.
 */

public class MinStack {

    private List<Integer> data = new ArrayList<Integer>();
    private List<Integer> mins = new ArrayList<Integer>();

    public void push(int num) throws Exception {
        data.add(num);
        if(mins.size() == 0) {
            // 初始化mins
            mins.add(0);
        } else {
            // 辅助栈mins push最小值的索引
            int min = getMin();
            if (num < min) {
                mins.add(data.size() - 1);
            }
        }
    }

    public int pop() throws Exception {
        // 栈空,抛出异常
        if(data.size() == 0) {
            throw new Exception("栈为空");
        }
        // pop时先获取索引
        int popIndex = data.size() - 1;
        // 获取mins栈顶元素,它是最小值索引
        int minIndex = mins.get(mins.size() - 1);
        // 如果pop出去的索引就是最小值索引,mins才出栈
        if(popIndex == minIndex) {
            mins.remove(mins.size() - 1);
        }
        return data.remove(data.size() - 1);
    }

    public int getMin() throws Exception {
        // 栈空,抛出异常
        if(data.size() == 0) {
            throw new Exception("栈为空");
        }
        // 获取mins栈顶元素,它是最小值索引
        int minIndex = mins.get(mins.size() - 1);
        return data.get(minIndex);
    }

}

【五分钟学算法面试现场】如何实现可以获取最小值的栈?

【五分钟学算法面试现场】如何实现可以获取最小值的栈?


【小史的疑惑】


吃饭的时候,小史提出了心中埋藏已久的疑惑。


【五分钟学算法面试现场】如何实现可以获取最小值的栈?

【五分钟学算法面试现场】如何实现可以获取最小值的栈?


吕老师:数据结构和算法的设计是一个程序员的内功,工作时虽然用不到这么细,但是你在学习其他知识的底层原理的时候,到处都是数据结构和算法。


【五分钟学算法面试现场】如何实现可以获取最小值的栈?

【五分钟学算法面试现场】如何实现可以获取最小值的栈?




五分钟学算法面试现场是互联网侦察推出的一个新的板块,旨在回放真实的面试过程,并对面试题进行全面解析,提供多种思路,比较优劣,希望对大家的面试有所帮助。


往期回顾:【五分钟学算法面试现场】如何判断一个数是否在40亿个整数中?


【五分钟学算法面试现场】如何实现可以获取最小值的栈?


原文始发于微信公众号(互联网侦察):【五分钟学算法面试现场】如何实现可以获取最小值的栈?