包含min函數(shù)的棧

作者丨程序員女朋友的貓

來(lái)源丨碼農(nóng)小說(shuō)家

0

我是一個(gè)無(wú)情的面試官。

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

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

招新人，填舊坑。

1

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

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

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

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

好了，已經(jīng)快一個(gè)半小時(shí)了，我只會(huì)問(wèn)最后一個(gè)問(wèn)題了。

他若回答上來(lái)了，我倆之蜜糖。

他若回答不上來(lái)，我倆之砒霜。

最后一題，必是算法。

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

2

我不急不忙，把題目念給他聽(tīng)。

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

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

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

此時(shí)此刻，他不像程序員，像演員。

他略加思索，說(shuō)了一個(gè)他自己都覺(jué)得不是合理的答案，但他還是說(shuō)了出來(lái)：

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

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

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

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

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

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

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

3

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

然后開(kāi)始默寫(xiě)答案，順便還把用作講解的圖畫(huà)了出來(lái)。

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

舉個(gè)例子

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

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

依次類(lèi)比。

下面是我寫(xiě)的代碼

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í)很好，這時(shí)候我已經(jīng)決定要他了，而且快中午，再不結(jié)束面試，食堂東坡肘子都快賣(mài)完了。

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

他的眼神從開(kāi)心，再到勝券在握，再到微微不屑。

臉上寫(xiě)滿了兩個(gè)字："就這"？

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

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

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

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

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

我知道，真正的對(duì)線才剛剛開(kāi)始。

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

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

其實(shí)我的目的很簡(jiǎn)單，不想錯(cuò)過(guò)他這個(gè)候選人，更不想錯(cuò)過(guò)東坡肘子。

魚(yú)和熊掌，我可兼得。