带min和max辅助函数的栈

设计一个特殊的栈,包含 min 函数。能够得到栈的最小元素。

要求函数 min、push 以及 pop 的时间复杂度都是 O(1)。

分析

由于时间复杂度的要求,我们不能用其他方法了,最简单的就是用空间换时间,给每个元素加一个min元素,表示压栈到现在最小的元素。

这样每次push时候,维护下data[top-1].min和当前val,取min值设到data[top].min即可。注意top=0时的特殊情况,min就是val。

特别提醒:企图整个栈共用一个min或者max辅助存储是错误的,因为一旦发生pop,min和max就会改变!

下面是代码,我还添加了一个max函数,也是复杂度O(1)的,原理一样,不解释了。

Leave a Reply

Your email address will not be published.