Lintcode12 Min Stack solution 题解


Implement a stack with min() function, which will return the smallest number in the stack.

It should support push, pop and min operation all in O(1) cost.

Notice:min operation will never be called if there is no number in the stack.


你实现的栈将支持push,pop 和 min 操作,所有操作要求都在O(1)时间内完成。




利用两个栈结构,其中一个是主要的正常stack,满足pop(), push()的O(1)时间要求,另外一个作为辅助的minStack,仅存入min的integer。 min = Integer.parseInt(minStack.peek().toString());

push()时,如果number >= min,则push到minStack上 pop()时,如果number == min,也从minStack上pop

题中的例子,最终stack为[2, 3, 1], minStack为 [2, 1]


A single golf clap? Or a long standing ovation?

By clapping more or less, you can signal to us which stories really stand out.