使用两个栈，一个栈用来保存当前栈中的元素功能和一个正常的栈没有区别

●　经常看到一篇文章前后的语境是割裂的，作者经常根据之前的一个优良解法提出更好的优化方式，但整篇文章都不提之前的解法是什么。这就导致初学者根本无法看懂；

●　几乎所有的书籍都忽略例子带来的引导作用，甚至还有不少书籍在阐述一个解法的时候只写伪代码，这就使得读者在看懂意思和自己真正能写出代码之间其实还有很多的路要走；

●　代码面试题目的特点是“多”、“杂”、“难”，从着手开始学习到最终达到自己想要的效果之间，自己对自己的评估根本无从谈起。“慢慢练吧，学海无涯”成为主要的心态，这就难免会产生怀疑的情绪；

●　看见一道新的面试题时还是会无从下手，因为之前的学习无法做到举一反三，对自己做过的题目缺乏总结和归纳。

难道“刷”题真的只适合聪明人玩？我不这么看，既然大多数内容处在有待商榷的地步，那我就去学习原论文吧。

当时一个人在国外，记得在初冬的一个下午，“刷”题已经两年之久，快吃晚饭的时候，我突然想起自己忘了吃午饭，就冲出家门去觅食。站在7-11门前的广场上，我拿着1.5美元的热狗和75美分的咖啡，微温的阳光撒在眼睛里，远远地望着即将消失的一天。我停下来，把咖啡放在斑驳的石头台子上，手里的热狗挺好看，香肠和洋葱都挺新鲜，清冷的空气吹过来，却让我的心绪更乱。旧金山的天空五彩斑斓，让漂泊者头晕目眩。哭得跟个鬼似的我除了想家，哪里敢想自己会出书呢？

当我意识到在网上很难搜到新鲜的题目时，我已经换了两家公司，反复实现了600多道题目，写了差不多10万行代码。原来只是为了找份工作而“刷”题这一初心早就忘了，变成了兴趣并坚持了这么久，我自己也感到意外。更奇怪的是，我已经完全乐在其中，同时交流欲望越来越强，时常和同事们展开这方面的讨论。发现很多书上的解法不是最优，很多题目其实和同事们讨论的做法更好，发现高手特别多，但好像都懒得动笔。

有一天，我看到自己写的题目，想到自己那些抓心挠肝的日子，突然觉得要不出书吧？我已经离不开这种感觉了，如果这不是真爱，那什么才是呢？

这不是一个励志的故事，是一个爱“刷”题的人决定把很多最优解讲出来，就这么简单。

实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。

【要求】

1.pop、push、getMin操作的时间复杂度都是O (1)。

2．设计的栈类型可以使用现成的栈结构。

【难度】

士　★☆☆☆

【解答】

在设计上我们使用两个栈，一个栈用来保存当前栈中的元素，其功能和一个正常的栈没有区别，这个栈记为stackData；另一个栈用于保存每一步的最小值，这个栈记为stackMin。具体的实现方式有两种。

第一种设计方案如下。

●　压入数据规则

假设当前数据为newNum，先将其压入stackData。然后判断stackMin是否为空：

●　如果为空，则newNum也压入stackMin。

●　如果不为空，则比较newNum和stackMin的栈顶元素中哪一个更小：

●　如果newNum更小或两者相等，则newNum也压入stackMin；

●　如果stackMin中栈顶元素小，则stackMin不压入任何内容。

举例：依次压入3、4、5、1、2、1的过程中，stockData和stackMin的变化如图1-1所示。

图1-1

●　弹出数据规则

先在stackData中弹出栈顶元素，记为value。然后比较当前stackMin的栈顶元素和value哪一个更小。

通过上文提到的压入规则可知，stackMin中存在的元素是从栈底到栈顶逐渐变小的，stackMin栈顶的元素既是stackMin栈的最小值，也是当前stackData栈的最小值。所以不会出现value比stackMin的栈顶元素更小的情况，value只可能大于或等于stackMin的栈顶元素。

当value等于stackMin的栈顶元素时，stackMin弹出栈顶元素；当value大于stackMin的栈顶元素时，stackMin不弹出栈顶元素；返回value。

很明显可以看出，压入与弹出规则是对应的。

●　查询当前栈中的最小值操作

由上文的压入数据规则和弹出数据规则可知，stackMin始终记录着stackData中的最小值，所以，stackMin的栈顶元素始终是当前stackData中的最小值。

方案一的代码实现如MyStack1类所示：

public class MyStack1 { private StackstackData; private StackstackMin; public MyStack1() { this.stackData = new Stack(); this.stackMin = new Stack(); } public void push(int newNum) { if (this.stackMin.isEmpty()) { this.stackMin.push(newNum); } else if (newNum <= this.getmin()) { this.stackMin.push(newNum); } this.stackData.push(newNum); } public int pop() { if (this.stackData.isEmpty()) { throw new RuntimeException("Your stack is empty."); } int value = this.stackData.pop(); if (value == this.getmin()) { this.stackMin.pop(); } return value; } public int getmin() { if (this.stackMin.isEmpty()) { throw new RuntimeException("Your stack is empty."); } return this.stackMin.peek(); } }

第二种设计方案如下。

●　压入数据规则

假设当前数据为newNum，先将其压入stackData。然后判断stackMin是否为空。

如果为空，则newNum也压入stackMin；如果不为空，则比较newNum和stackMin的栈顶元素中哪一个更小：

如果newNum更小或两者相等，则newNum也压入stackMin；如果stackMin中栈顶元素小，则把stackMin的栈顶元素重复压入stackMin，即在栈顶元素上再压入一个栈顶元素。

举例：依次压入3、4、5、1、2、1的过程中，stockData和stackMin的变化如图1-2所示。

图1-2

●　弹出数据规则

在stackData中弹出数据，弹出的数据记为value；弹出stackMin中的栈顶；返回value。

很明显可以看出，压入与弹出规则是对应的。

●　查询当前栈中的最小值操作

由上文的压入数据规则和弹出数据规则可知，stackMin始终记录着stackData中的最小值，所以stackMin的栈顶元素始终是当前stackData中的最小值。