在《剑指Offer》一书看到的题目。要求push, pop, min的时间复杂度都为O(1) 一开始我能想到的方法是，用一个指针指向当前栈中最小的元素，当有新元素进来时， 和当前最小元素比较，如果较小则更新指针，否则不做更改。但是当元素出栈时，就出现 问题了，如果出栈的是最小的那个元素，那我这个指针应该指向哪里呢？ 再想，如果我用2个指针，一个指向次小元素，一个指向最小元素，会怎样呢？其实也不行， 这样是换汤不换药，当最小元素出栈时，次小元素也不知道指向哪里？ 没办法，我记录所有元素的顺序就行了。这样的话，空间复杂度会翻倍，但是这是让3个 函数时间复杂度都为O(1)以空间换时间的办法。 实际上...

阅读更多