包含min函數(shù)的棧

作者丨程序員女朋友的貓

來源丨碼農(nóng)小說家

0

我是一個無情的面試官。

面人無數(shù)，掛人無數(shù)。

若想過我的面試，標(biāo)準(zhǔn)只有一個，那就是公司很缺人。

招新人，填舊坑。

1

今天是我的第1001次當(dāng)面試官，要求卻不是千里挑一，而是一擊必中。

因?yàn)槲艺衅傅腒PI快完不成了。

對面的小伙子，我和他從HTTP協(xié)議談到負(fù)載均衡，從類的命名規(guī)范談到JVM調(diào)優(yōu)，凡是搬磚用不到的，我們都聊了一遍，相談甚歡。

我知道我們是一路人，都是為面試而學(xué)習(xí)。

好了，已經(jīng)快一個半小時了，我只會問最后一個問題了。

他若回答上來了，我倆之蜜糖。

他若回答不上來，我倆之砒霜。

最后一題，必是算法。

行業(yè)規(guī)則，我必遵從。

2

我不急不忙，把題目念給他聽。

重新定義一個棧的數(shù)據(jù)結(jié)構(gòu) ，在該類型中實(shí)現(xiàn)一個能夠得到棧的最小值的min函數(shù)，并且調(diào)用push pop min函數(shù)的時間復(fù)雜度都是O(1)

講完題目，他的眼神從驚喜，到思索，再到不解。

我便知道他刷過這道題，他也知道自己刷過這道題，但是他還是假裝不知道自己刷過這道題。

此時此刻，他不像程序員，像演員。

他略加思索，說了一個他自己都覺得不是合理的答案，但他還是說了出來：

"我首先想到的是，新增一個成員變量來存放最小的元素，每次入棧的時候，如果新元素比該成員變量的值還小的時候，則將該成員變量更新為新元素的值。"

我微微一笑："那如果記錄最小的元素已經(jīng)出棧了，如何得到下一個最小的元素呢？"。

他假裝恍然大悟："是啊 ，確實(shí)。"。

于是他拿著筆，看著紙，仿佛在思考怎么表演的這答案更是自己想出來的。

我知道，這個是面試套路，他若直接說出來最佳答案，身為面試官的我難免不會拓展這個題目，相反，他要假裝說出來一個不太好的答案，在我的提示下，他聰明的想到了最優(yōu)解法。

我有了面子，畢竟在我的指導(dǎo)下他才解決問題。

他有了里子，在緊張的環(huán)境下他仍能快速思考。

3

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

然后開始默寫答案，順便還把用作講解的圖畫了出來。

寫完之后，他娓娓道來："您看，確實(shí)是僅僅記錄最小元素是不夠的，還要記錄當(dāng)前棧中第二小元素，第三小元素。。。為了保存這些元素，我采用了一個輔助棧"。

舉個例子

所以 ，如果我一直將當(dāng)前最小元素壓入輔助棧，那么就能保證輔助棧的棧頂元素都是最小元素。

如果出棧的時候，主棧彈出數(shù)據(jù)之后，輔助棧會一起彈出數(shù)據(jù)，即輔助棧的棧頂一直都是當(dāng)前棧的最小元素。

依次類比。

下面是我寫的代碼

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();
    }
}

其實(shí)很好，這時候我已經(jīng)決定要他了，而且快中午，再不結(jié)束面試，食堂東坡肘子都快賣完了。

于是我贊賞到："確實(shí)不錯，代碼很規(guī)范，可以的。"

他的眼神從開心，再到勝券在握，再到微微不屑。

臉上寫滿了兩個字："就這"？

仿佛主客場完全反轉(zhuǎn)，下一秒就有可能拒掉我們的offer。

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

我頓了一頓："那我們換個思路，我再拓展一個題目"

重新定義一個隊(duì)列，并實(shí)現(xiàn)函數(shù) max_value 得到隊(duì)列里的最大值，要求函數(shù)max_value、push_back 和 pop_front 的均攤時間復(fù)雜度都是O(1)。

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

我知道，真正的對線才剛剛開始。

為了顯示我的人道主義，我提示到，今天先到這吧，咱倆加個微信，不用現(xiàn)在想，回頭把代碼發(fā)給我就行。

他舒了一口氣，但是不知道我這樣做的目的。

其實(shí)我的目的很簡單，不想錯過他這個候選人，更不想錯過東坡肘子。

魚和熊掌，我可兼得。