Untitled.png

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

这是一道面试高频题,leetcode easy难度,这道题难在出栈时如何维护最小值,本文将介绍三种方式

1. 维护最小值, 错误,因为它无法应对出栈情况.
2. 基于辅助栈, 凑合用 时间复杂度O(1),空间复杂度O(n)
3. 最小值+辅助栈. 前面两者优点的融合,精彩绝伦 时间复杂度O(1),空间复杂度O(1)

方式1 维护最小值

一个最容易想到也最简单的方式是维护一个数值表示最小值.每当有更小的数值入栈就将其更新.但是它无法应对出栈的情况.

例如我们将下图中的序号8,7依次出栈

1. 第一次4出栈,大于当前最小值,可以判定最小值还是-2
2. 第二次-2出栈,等于当前最小值, 无法判定新的最小值

这种方式无法实现但是其部分思路可以借鉴.

方式2 基于辅助栈

维护一个辅助栈,出入栈与原始栈保持一致,唯一的区别是: 入栈时辅助栈添加的是最小值

下面的图表演示了压栈/出栈时辅助栈是如何维护最新值： 最小值就是辅助栈栈顶元素

先来看入栈

E[1]=1入栈,辅助栈中1入栈,栈顶为1,最小值为1

E[2]=3入栈,辅助栈中1入栈,栈顶为1,最小值为1

.....

E[6]=-1入栈,辅助栈中-1入栈.栈顶为-1,最小值为-1

再来看出栈流程

序号6出栈,辅助栈中-1出栈, 栈顶为1,最小值为1

序号5出栈,辅助栈中1出栈,栈顶为1,最小值为1.

辅助栈方式的时间复杂度是O(1),空间复杂度为O(n),下面介绍一种更为优秀的方式： 最小值+辅助栈，它的时间复杂度和空间复杂度均为O(1)

方式3 最小值+辅助栈

维护最小值的方式给我们的启示: 利用当前最小值和入栈值的关系可以推算新的最小值；辅助栈的方式给我们带来一些启示: 栈里存储的值可以不是入栈值.

结合这两点, 我们努力的方向是 寻找入栈值,最小值和存储值的关系.

在入栈时已知入栈值和最小值，求存储值.在出栈时由存储值和最小值求新的最小值.

看着比较绕,但是他的实质就是数学中的一个简单概念,已知X+Y=Z中的X,Y.求Z

难怪有人说京城三万月薪以下的码农只需要初中数学

下面我们就结合这个思路寻找特征

将序号为n的元素E[n]入栈时, 当前最小值M[n-1]和入栈值E[n]有如下关系.

入栈值  < 当前最小值   ==> 出现新的最小值 => E[n] < M[n-1]  ==> M[n-1] - E[n] > 0    @1
入栈值为第一个元素     ==> 出现新的最新值 ==> M[n] = E[n] @2
入栈值  >= 当前最小值  ==> 最小值不变 M[n]=M[n-1] ==> E[n] >= M[n-1]    ==> M[n-1]-E[n] <= 0 @3

我们可以将M[n-1]-E[n]当做存储值,由@1,@3得@4, 由@2得@5

存储值S[n] = M[n-1] - E[n]                  n > 1    @4     
                     = M[n] -E[n] = E[n] - E[n] = 0  n = 1     @5    

在出栈时根据存储值S[n]的正负推算出最小值,由于最小值的下标与另外两个值有错位,所以这里求的是M[n-1]下面这个两个公式结合入栈流程会更好懂

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:

入栈时,存储的值S[n]由公式@4和@5计算得出;维护一个数值MIN表示最小值,每当有更小的值就将其更新

出栈时 由公式@6和@7更新最小值MIN,由公式@8,@9计算原始的入栈值

结合下面这个例子食用更佳

首先,入栈流程 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

再来看下出栈流程

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]无意义
@9 ==> E[1] = M[1] = 1

方式3是目前性能最佳的方式(双O(1)),也是最难理解的,笔者最初也是在leetcode上看的题解,读者可以结合例子和公式思考.

后记

本文介绍了最小栈的三种"解决"方式: 错误的方式,正确的方式,高效的方式.其中高效的方式结合了前两者的优点,达成了性能最优.

软件设计的哲学(A PHILOSOPHY OF SOFTWARE DESIGN)这本书有一章的主题是设计两次,本文特别契合这个主题,在这里跟大家分享下

尝试选择那些彼此截然不同的方法，这样你会学到更多。即使您确定只有一种合理的方法，无论您认为第二种设计有多糟糕，都要考虑采用第二种设计。思考该设计的弱点并将其与其他设计的特点进行对比将是有益的。

leetcode题目链接 https://leetcode-cn.com/problems/min-stack/