设计一个有getMin功能的栈
【题目】
实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作。
【要求】
1.pop、push、getMin操作的时间复杂度都是O（1）。
2.设计的栈类型可以使用现成的栈结构。
【难度】
士 ★☆☆☆
【解答】
在设计时，我们使用两个栈，一个栈用来保存当前栈中的元素，其功能和一个正常的栈没有区别，这个栈记为stackData；另一个栈用于保存每一步的最小值，这个栈记为stackMin。具体的实现方式有两种。
第一种设计方案
（1）压入数据规则
假设当前数据为newNum，先将其压入stackData。然后判断stackMin是否为空：
● 如果为空，则newNum也压入stackMin。
● 如果不为空，则比较newNum和stackMin的栈顶元素中哪一个更小：
如果newNum更小或两者相等，则newNum也压入stackMin；
如果stackMin中栈顶元素小，则stackMin不压入任何内容。
举例：依次压入3、4、5、1、2、1的过程中，stackData和stackMin的变化如图1-1所示。
图1-1
（2）弹出数据规则
先在 stackData 中弹出栈顶元素，记为 value。然后比较当前 stackMin 的栈顶元素和 value哪一个更小。
通过上文提到的压入规则可知，stackMin 中存在的元素是从栈底到栈顶逐渐变小的，stackMin栈顶的元素既是stackMin栈的最小值，也是当前stackData栈的最小值。所以不会出现value比stackMin的栈顶元素更小的情况，value只可能大于或等于stackMin的栈顶元素。
当value等于stackMin的栈顶元素时，stackMin弹出栈顶元素；当value大于stackMin的栈顶元素时，stackMin不弹出栈顶元素，返回value。
很明显可以看出，压入与弹出规则是对应的。
（3）查询当前栈中的最小值操作
由上文的压入数据规则和弹出数据规则可知，stackMin始终记录着stackData中的最小值。所以，stackMin的栈顶元素始终是当前stackData中的最小值。
方案一的代码实现如MyStack1类所示：
第二种设计方案
（1）压入数据规则
假设当前数据为newNum，先将其压入stackData。然后判断stackMin是否为空。
如果为空，则newNum也压入stackMin；如果不为空，则比较newNum和stackMin的栈顶元素中哪一个更小。
如果newNum更小或两者相等，则newNum也压入stackMin；如果 stackMin 中栈顶元素小，则把stackMin的栈顶元素重复压入stackMin，即在栈顶元素上再压入一个栈顶元素。
举例：依次压入3、4、5、1、2、1的过程中，stackData和stackMin的变化如图1-2所示。
图1-2
（2）弹出数据规则
在stackData中弹出数据，弹出的数据记为value；弹出stackMin中的栈顶，返回value。
很明显可以看出，压入与弹出规则是对应的。
（3）查询当前栈中的最小值操作
由上文的压入数据规则和弹出数据规则可知，stackMin始终记录着stackData中的最小值，所以stackMin的栈顶元素始终是当前stackData中的最小值。
方案二的代码实现如MyStack2类所示：
【点评】
方案一和方案二其实都是用 stackMin 栈保存着 stackData 每一步的最小值。共同点是所有操作的时间复杂度都为O（1）、空间复杂度都为O（n）。区别是：方案一中stackMin压入时稍省空间，但是弹出操作稍费时间；方案二中stackMin压入时稍费空间，但是弹出操作稍省时间。