题目:实现一个栈,带有出栈(pop),入栈(push),取最小元素(getMin)三个方法。要保证这三个方法的时间复杂度都是O(1)。
解法:
1. 设原有的栈叫做栈A,此时创建一个额外的栈B,用于辅助原栈A。
2. 当第一元素进入栈A的时候,让新元素的下标进入栈B。这个唯一的元素是是栈
A的当前最小值。(考虑到栈中元素可能不是类对象,所以B栈存储的是A栈的
元素的下标)
3. 每当新元素进入栈A时,比较新元素和栈A当前最小值得大小,如果小于栈A当
前最小值,则让新元素的下标进入栈B,此时栈B的栈顶元素就是栈A当前最小
值的下标。
4. 每当栈A有元素出栈时,如果出栈元素是栈A当前最小值,则让栈B的栈顶元素
页出栈。此时栈B余下的栈顶元素所指向的,是栈A当中原本第二小的元素,代
替刚才的出栈元素成为了栈A的当前最小值。
5. 当调用getMin方法的时候,直接返回栈B的栈顶所指向的栈A对应的元素即可。
这个解法中进栈、出栈、取最小值的时间复杂度都是O(1),最坏情况复杂度是O(N)。??