题目
设计一个栈, 在实现栈的基本功能基础上, 还能够返回栈中最小的元素
算法分析
最直观的想法, 就是直接使用栈, 每次要想拿到最小元素时, 就从栈A中全部出栈, 然后寻找其中的最小元素, 之后在将元素全部压入栈A, 要实现这个全部取出在全部压入的操作, 显然需要一个临时的数组结构, 最好也是栈结构.
那么, 既然用到了另外的栈, 我们又何必做全部出栈再全部入栈这么费时的操作, 将另一个栈用作保存最小元素不就好了么.
到这里, 我们决定使用两个栈来实现这个功能, 一个栈用于保存数据, 一个栈用于保存当前的最小值, 新的问题又来了, 数据栈的入出自不必说, 那么最小值的栈该如何实现入栈和出栈的操作, 才能保证每次栈顶都是当前的最小值呢?
最小值栈的设计思路一:
数据入栈时, 将最小值保存在最小值栈中, 若最小值无更新, 则重复入最小值栈, 这样在数据出栈时, 最小值栈跟着出栈即可.
其压入数据的具体规则应如下(若当前压入数据num):
- 将num如数据栈
- 判断最小值栈是否为空
- 若最小值栈为空, 则num入最小值栈
- 若最小值栈不为空, 则判断num与最小值栈栈顶元素min的大小
- 若min >= num, 则num入最小值栈
- 若min < num, 则min入最小值栈
其压入数据过程如图所示:
出栈操作与入栈操作对应, 每次数据栈出栈时, 最小值栈也同步出栈即可
简单的Java代码实现如下, 代码不够完善, 仅提供思路:
最小值栈的设计思路二:
上面的思路导致两个栈大小相等, 显然最小值栈中存在很多重复的元素, 如何节省最小值栈的空间呢?
将最小值栈顶保存当前栈的最小值, 若有新数据入栈时, 判断其与最小值栈栈顶元素大小, 判断是否需要更新最小值, 若新值更小或者相等的话, 则压入最小值栈(相等也入栈是因为出栈的时候, 可以直接出栈, 不用顾虑太多), 如此即可使的最小值栈栈顶元素为当前栈的最小值
其压入数据的具体规则应如下(若当前压入数据num):
- 将num入数据栈
- 判断最小值栈是否为空
- 若最小值栈为空, 则num入最小值栈, 不做操作
- 若最小值栈不为空, 则将num与最小值栈栈顶元素min进行比较
- 若min>=num, 则将num入栈
- 若min
其压入数据过程如下图所示:
压入数据的规则有了, 那么弹出数据的规则也就有了, 因为总是将更小或相等的元素压入最小值栈, 所以最小值栈中的元素上面的总是小于等于下面的元素, 故在弹出数据时进行判断即可, 若是最小值则弹出, 具体如下(弹出数据num):
- 判断num与最小值栈栈顶元素min的大小
- 若 num > min, 不做操作
- 若num == min, 弹出最小值栈栈顶元素(因为入栈时没出现一个, 都入栈一次, 所以出栈时每次也都要出栈了)
- 若num < min, 异常了吧, 咱们是将最小的压入栈顶, 若出现这种情况, 伤心
简单的Java代码实现如下, 代码不够完善, 仅提供思路:
当然, 并不是思路二就比思路一要号, 思路二虽然节省了空间, 但是在出栈操作时要进行判断, 稍费些时间.
閱讀更多 牛牛的編程之路 的文章
