包含min函数的栈

作者丨程序员女朋友的猫

来源丨码农小说家

0

我是一个无情的面试官。

面人无数，挂人无数。

若想过我的面试，标准只有一个，那就是公司很缺人。

招新人，填旧坑。

1

今天是我的第1001次当面试官，要求却不是千里挑一，而是一击必中。

因为我招聘的KPI快完不成了。

对面的小伙子，我和他从HTTP协议谈到负载均衡，从类的命名规范谈到JVM调优，凡是搬砖用不到的，我们都聊了一遍，相谈甚欢。

我知道我们是一路人，都是为面试而学习。

好了，已经快一个半小时了，我只会问最后一个问题了。

他若回答上来了，我俩之蜜糖。

他若回答不上来，我俩之砒霜。

最后一题，必是算法。

行业规则，我必遵从。

2

我不急不忙，把题目念给他听。

重新定义一个栈的数据结构 ，在该类型中实现一个能够得到栈的最小值的min函数，并且调用push pop min函数的时间复杂度都是O(1)

讲完题目，他的眼神从惊喜，到思索，再到不解。

我便知道他刷过这道题，他也知道自己刷过这道题，但是他还是假装不知道自己刷过这道题。

此时此刻，他不像程序员，像演员。

他略加思索，说了一个他自己都觉得不是合理的答案，但他还是说了出来：

"我首先想到的是，新增一个成员变量来存放最小的元素，每次入栈的时候，如果新元素比该成员变量的值还小的时候，则将该成员变量更新为新元素的值。"

我微微一笑："那如果记录最小的元素已经出栈了，如何得到下一个最小的元素呢？"。

他假装恍然大悟："是啊 ，确实。"。

于是他拿着笔，看着纸，仿佛在思考怎么表演的这答案更是自己想出来的。

我知道，这个是面试套路，他若直接说出来最佳答案，身为面试官的我难免不会拓展这个题目，相反，他要假装说出来一个不太好的答案，在我的提示下，他聪明的想到了最优解法。

我有了面子，毕竟在我的指导下他才解决问题。

他有了里子，在紧张的环境下他仍能快速思考。

3

果然，不久他就说：“我有思路了！”

然后开始默写答案，顺便还把用作讲解的图画了出来。

写完之后，他娓娓道来："您看，确实是仅仅记录最小元素是不够的，还要记录当前栈中第二小元素，第三小元素。。。为了保存这些元素，我采用了一个辅助栈"。

举个例子

所以 ，如果我一直将当前最小元素压入辅助栈，那么就能保证辅助栈的栈顶元素都是最小元素。

如果出栈的时候，主栈弹出数据之后，辅助栈会一起弹出数据，即辅助栈的栈顶一直都是当前栈的最小元素。

依次类比。

下面是我写的代码

import java.util.Stack;

class MinStack {

    private Stack<Integer> stack;
    private Stack<Integer> minStack;

    public MinStack() {
        stack=new Stack<>();
        minStack=new Stack<>();
    }

    public void push(int x) {
        stack.push(x);
        if(minStack.isEmpty())
            minStack.push(x);
        else
            minStack.push(minStack.peek()<x ? minStack.peek():x);
    }

    public void pop() {
        stack.pop();
        minStack.pop();
    }

    public int min() {
        return minStack.peek();
    }
}

其实很好，这时候我已经决定要他了，而且快中午，再不结束面试，食堂东坡肘子都快卖完了。

于是我赞赏到："确实不错，代码很规范，可以的。"

他的眼神从开心，再到胜券在握，再到微微不屑。

脸上写满了两个字："就这"？

仿佛主客场完全反转，下一秒就有可能拒掉我们的offer。

那一刻我决定，我要教他做事。

我顿了一顿："那我们换个思路，我再拓展一个题目"

重新定义一个队列，并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。

他的眼神从失落，再到迷惑不解，再到无可奈何。

我知道，真正的对线才刚刚开始。

为了显示我的人道主义，我提示到，今天先到这吧，咱俩加个微信，不用现在想，回头把代码发给我就行。

他舒了一口气，但是不知道我这样做的目的。

其实我的目的很简单，不想错过他这个候选人，更不想错过东坡肘子。

鱼和熊掌，我可兼得。