前言
遇到一道面试题,题目大概意思如下:
使用两个普通栈实现一个特殊栈,使得pop、push、min三个函数的都是复杂度为O(1)的操作,min函数是获得当前栈的最小值。
初步想法
1.要实现min函数为(1)操作,当时第一想法是事先需要算好当前最小值,于是会想到用一个值来保存当前栈中最小值元素,然后push和pop操作的时候维护这个值。这样min,push都是O(1)了,但pop可不是,如果当前弹出的是最小值,需要从新寻找当前元素的最小值,这个就不是o(1)了。
2.而且上面方法没有用到另外一