文章目录

1. 1. Min Stack

Min Stack

---

这个问题是要求我们实现一个栈，使得栈能够有这四个功能函数push(x), pop(), top(), getMin()。其中返回最小值需要在常数时间内完成。

这题目的核心在于建立两个数组：一个用来存正常的堆栈信息，另一个是用来记录最小值得。这里还要用到一个想法就是当堆栈的第一个数弹出去之后，大于等于它的数就不会是最小值了。虽然是句废话，但可以帮助我们建立最小值的数组：在建立堆栈的时候，我们就不用去记录比第一个数大的数了。