作者 | channingbreeze

责编 | 胡巍巍

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

今天他又去BAT中的一家面试了。简单的自我介绍后，面试官给了小史一个问题。

面试现场

题目：我现在需要实现一个栈，这个栈除了可以进行普通的push、pop操作以外，还可以进行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进来的值，还是栈为空，就不得而知了。

小史咬咬牙：那就再定义一个类，里面包括一个int的data、和一个boolean的isSuccess，正常情况下isSuccess是true，栈为空的话，isSuccess是false。这样就能区分开了吧？

小史突然一拍大腿：对哦，我可以用一个包装类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);
    }

}

小史的疑惑

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

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

作者简介：channingbreeze，国内某互联网公司全栈开发。

声明：本文为作者投稿，版权归对方所有。作者独立观点，不代表 CSDN 立场。

_“ 征稿啦 _”

CSDN 公众号秉持着「与千万技术人共成长」理念，不仅以「极客头条」、「畅言」栏目在第一时间以技术人的独特视角描述技术人关心的行业焦点事件，更有「技术头条」专栏，深度解读行业内的热门技术与场景应用，让所有的开发者紧跟技术潮流，保持警醒的技术嗅觉，对行业趋势、技术有更为全面的认知。

如果你有优质的文章，或是行业热点事件、技术趋势的真知灼见，或是深度的应用实践、场景方案等的新见解，欢迎联系 CSDN 投稿，联系方式：微信（guorui_1118，请备注投稿+姓名+公司职位），邮箱（guorui@csdn.net）。