Untitled.png

設(shè)計(jì)一個(gè)支持 push ，pop ，top 操作，并能在常數(shù)時(shí)間內(nèi)檢索到最小元素的棧。

這是一道面試高頻題,leetcode easy難度,這道題難在出棧時(shí)如何維護(hù)最小值,本文將介紹三種方式

1. 維護(hù)最小值, 錯(cuò)誤,因?yàn)樗鼰o(wú)法應(yīng)對(duì)出棧情況.
2. 基于輔助棧, 湊合用 時(shí)間復(fù)雜度O(1),空間復(fù)雜度O(n)
3. 最小值+輔助棧. 前面兩者優(yōu)點(diǎn)的融合,精彩絕倫 時(shí)間復(fù)雜度O(1),空間復(fù)雜度O(1)

方式1 維護(hù)最小值

一個(gè)最容易想到也最簡(jiǎn)單的方式是維護(hù)一個(gè)數(shù)值表示最小值.每當(dāng)有更小的數(shù)值入棧就將其更新.但是它無(wú)法應(yīng)對(duì)出棧的情況.

例如我們將下圖中的序號(hào)8,7依次出棧

1. 第一次4出棧,大于當(dāng)前最小值,可以判定最小值還是-2
2. 第二次-2出棧,等于當(dāng)前最小值, 無(wú)法判定新的最小值

這種方式無(wú)法實(shí)現(xiàn)但是其部分思路可以借鑒.

方式2 基于輔助棧

維護(hù)一個(gè)輔助棧,出入棧與原始棧保持一致,唯一的區(qū)別是: 入棧時(shí)輔助棧添加的是最小值

下面的圖表演示了壓棧/出棧時(shí)輔助棧是如何維護(hù)最新值： 最小值就是輔助棧棧頂元素

先來(lái)看入棧

E[1]=1入棧,輔助棧中1入棧,棧頂為1,最小值為1

E[2]=3入棧,輔助棧中1入棧,棧頂為1,最小值為1

.....

E[6]=-1入棧,輔助棧中-1入棧.棧頂為-1,最小值為-1

再來(lái)看出棧流程

序號(hào)6出棧,輔助棧中-1出棧, 棧頂為1,最小值為1

序號(hào)5出棧,輔助棧中1出棧,棧頂為1,最小值為1.

輔助棧方式的時(shí)間復(fù)雜度是O(1),空間復(fù)雜度為O(n),下面介紹一種更為優(yōu)秀的方式： 最小值+輔助棧，它的時(shí)間復(fù)雜度和空間復(fù)雜度均為O(1)

方式3 最小值+輔助棧

維護(hù)最小值的方式給我們的啟示: 利用當(dāng)前最小值和入棧值的關(guān)系可以推算新的最小值；輔助棧的方式給我們帶來(lái)一些啟示: 棧里存儲(chǔ)的值可以不是入棧值.

結(jié)合這兩點(diǎn), 我們努力的方向是 尋找入棧值,最小值和存儲(chǔ)值的關(guān)系.

在入棧時(shí)已知入棧值和最小值，求存儲(chǔ)值.在出棧時(shí)由存儲(chǔ)值和最小值求新的最小值.

看著比較繞,但是他的實(shí)質(zhì)就是數(shù)學(xué)中的一個(gè)簡(jiǎn)單概念,已知X+Y=Z中的X,Y.求Z

難怪有人說(shuō)京城三萬(wàn)月薪以下的碼農(nóng)只需要初中數(shù)學(xué)

下面我們就結(jié)合這個(gè)思路尋找特征

將序號(hào)為n的元素E[n]入棧時(shí), 當(dāng)前最小值M[n-1]和入棧值E[n]有如下關(guān)系.

入棧值  < 當(dāng)前最小值   ==> 出現(xiàn)新的最小值 => E[n] < M[n-1]  ==> M[n-1] - E[n] > 0    @1
入棧值為第一個(gè)元素     ==> 出現(xiàn)新的最新值 ==> M[n] = E[n] @2
入棧值  >= 當(dāng)前最小值  ==> 最小值不變 M[n]=M[n-1] ==> E[n] >= M[n-1]    ==> M[n-1]-E[n] <= 0 @3

我們可以將M[n-1]-E[n]當(dāng)做存儲(chǔ)值,由@1,@3得@4, 由@2得@5

存儲(chǔ)值S[n] = M[n-1] - E[n]                  n > 1    @4     
                     = M[n] -E[n] = E[n] - E[n] = 0  n = 1     @5    

在出棧時(shí)根據(jù)存儲(chǔ)值S[n]的正負(fù)推算出最小值,由于最小值的下標(biāo)與另外兩個(gè)值有錯(cuò)位,所以這里求的是M[n-1]下面這個(gè)兩個(gè)公式結(jié)合入棧流程會(huì)更好懂

M[n-1]= M[n]+S[n]   S[n] > 0    @6
                M[n]        S[n] <= 0   @7

同理由公式@4,@5推算入棧值E[n]

E[n]= M[n-1] - S[n] n > 1 @8
        = M[n]          n = 1 @9 

有了上面的這些公式,我們可以得出方式3:

入棧時(shí),存儲(chǔ)的值S[n]由公式@4和@5計(jì)算得出;維護(hù)一個(gè)數(shù)值MIN表示最小值,每當(dāng)有更小的值就將其更新

出棧時(shí) 由公式@6和@7更新最小值MIN,由公式@8,@9計(jì)算原始的入棧值

結(jié)合下面這個(gè)例子食用更佳

首先,入棧流程 E[1]=1入棧

@5 =? S[1]=0

@2 =? MIN=M[1] = E[1] = 1

然后E[2]=3入棧

@4 ==> S[2] = M[1] -E[2] = -2
@3 ==> MIN = M[2] = M[1] = 1

...

之后E[6]=-1入棧

@4 ==> S[6] = M[5]-E[6] = 2
@1 ==> MIN = M[6] = E[6] = -1

再來(lái)看下出棧流程

S[8]=-6出棧

@7 ==> MIN = [7] = M[8] =-2
@8 ==> E[8] = M[7] - S[8]= -2-(-6) = 4

S[7]=1 出棧

@6 ==> MIN = M[6] = M[7] + S[7] = -2 +1 = -1
@8 ==> E[7] = M[6] -S[7] = -1 - 1 = -2

......

S[2]=-2出棧

@7 ==> MIN = M[1] = M[2] = 1
@8 ==> E[2] = M[1] -S[2] = 1-(-2) = 3 

S[1]=0出棧

M[0]無(wú)意義
@9 ==> E[1] = M[1] = 1

方式3是目前性能最佳的方式(雙O(1)),也是最難理解的,筆者最初也是在leetcode上看的題解,讀者可以結(jié)合例子和公式思考.

后記

本文介紹了最小棧的三種"解決"方式: 錯(cuò)誤的方式,正確的方式,高效的方式.其中高效的方式結(jié)合了前兩者的優(yōu)點(diǎn),達(dá)成了性能最優(yōu).

軟件設(shè)計(jì)的哲學(xué)(A PHILOSOPHY OF SOFTWARE DESIGN)這本書(shū)有一章的主題是設(shè)計(jì)兩次,本文特別契合這個(gè)主題,在這里跟大家分享下

嘗試選擇那些彼此截然不同的方法，這樣你會(huì)學(xué)到更多。即使您確定只有一種合理的方法，無(wú)論您認(rèn)為第二種設(shè)計(jì)有多糟糕，都要考慮采用第二種設(shè)計(jì)。思考該設(shè)計(jì)的弱點(diǎn)并將其與其他設(shè)計(jì)的特點(diǎn)進(jìn)行對(duì)比將是有益的。

leetcode題目鏈接 https://leetcode-cn.com/problems/min-stack/