Untitled.png
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
这是一道面试高频题,leetcode easy难度,这道题难在出栈时如何维护最小值,本文将介绍三种方式
- 维护最小值, 错误,因为它无法应对出栈情况.
- 基于辅助栈, 凑合用 时间复杂度O(1),空间复杂度O(n)
- 最小值+辅助栈. 前面两者优点的融合,精彩绝伦 时间复杂度O(1),空间复杂度O(1)
方式1 维护最小值
一个最容易想到也最简单的方式是维护一个数值表示最小值.每当有更小的数值入栈就将其更新.但是它无法应对出栈的情况.
例如我们将下图中的序号8,7依次出栈
| 序号 N | 入栈值 E | 最小值 M | 出栈后的最小值 |
|---|---|---|---|
| 1 | 1 | 1 | |
| 2 | 3 | 1 | |
| 3 | 2 | 1 | |
| 4 | 5 | 1 | |
| 5 | 7 | 1 | |
| 6 | -1 | -1 | |
| 7 | -2 | -2 | ? |
| 8 | 4 | -2 | -2 |
- 第一次4出栈,大于当前最小值,可以判定最小值还是-2
- 第二次-2出栈,等于当前最小值, 无法判定新的最小值
这种方式无法实现但是其部分思路可以借鉴.
方式2 基于辅助栈
维护一个辅助栈,出入栈与原始栈保持一致,唯一的区别是: 入栈时辅助栈添加的是最小值
下面的图表演示了压栈/出栈时辅助栈是如何维护最新值： 最小值就是辅助栈栈顶元素
| 序号 N | 入栈值 E | 栈 S(栈顶<--栈底) | 辅助栈 A(栈顶<--栈底) | 最小值 M |
|---|---|---|---|---|
| 1 | 1 | 1 | 1 | 1 |
| 2 | 3 | 3,1 | 1,1 | 1 |
| 3 | 2 | 2,3,1 | 1,1,1 | 1 |
| 4 | 5 | 5,2,3,1 | 1,1,1,1 | 1 |
| 5 | 7 | 7,5,2,3,1 | 1,1,1,1,1 | 1 |
| 6 | -1 | -1,7,5,2,3,1 | -1,1,1,1,1,1 | -1 |
| 7 | -2 | -2,-1,7,5,2,3,1 | -2,-1,1,1,1,1,1 | -2 |
| 8 | 4 | 4,-2,-1,7,5,2,3,1 | -2,-2,-1,1,1,1,1,1 | -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计算原始的入栈值
结合下面这个例子食用更佳
| 序号 N | 入栈值 E | 最小值 M | 栈 S |
|---|---|---|---|
| 1 | 1 | 1 | 0 |
| 2 | 3 | 1 | -2,0 |
| 3 | 2 | 1 | -1,-2,0 |
| 4 | 5 | 1 | -4,-1,-2,0 |
| 5 | 7 | 1 | -6,-4,-1,-2,0 |
| 6 | -1 | -1 | 2,-6,-4,-1,-2,0 |
| 7 | -2 | -2 | 1,2,-6,-4,-1,-2,0 |
| 8 | 4 | -2 | -6,1,2,-6,-4,-1,-2,0 |
首先,入栈流程 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/
网友评论