【 题目 】

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

【 要求 】

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

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

【 解答 】

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

第一种设计方案如下。

.压入数据规则。

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

· 如果为空，则 n ewN也压入 atackMin .

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

· 如果 n ewNum 更小或两者相等，则 newNum 也压入 atackMin

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

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

弹出数据规则

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

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

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

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

· 查询当前栈中最小值操作

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

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

第二种方案，小伙伴们可以一起交流一下哦

CSDN社群火爆招募中：https://blog.csdn.net/CSDNedu/article/details/80063505?utm_source=zwqt