2.5 如何用O（1）的时间复杂度求栈中最小元素

【出自XM面试题】

难度系数：★★★★☆

被考察系数：★★★★☆

分析与解答：

由于栈具有后进先出的特点，因此push和pop只需要对栈顶元素进行操作。如果使用上述的实现方式，只能访问到栈顶的元素，无法得到栈中最小的元素。当然，可以用另外一个变量来记录栈底的位置，通过遍历栈中所有的元素找出最小值，但是这种方法的时间复杂度为O（N），那么如何才能用O（1）的时间复杂度求出栈中最小的元素呢？

在算法设计中，经常会采用空间来换取时间的方式来提高时间复杂度。也就是说，采用额外的存储空间来降低操作的时间复杂度。具体而言，在实现时使用两个栈结构，一个栈用来存储数据，另外一个栈用来存储栈的最小元素。实现思路如下：如果当前入栈的元素比原来栈中的最小值还小，则把这个值压入保存最小元素的栈中；在出栈时，如果当前出栈的元素恰好为当前栈中的最小值，保存最小值的栈顶元素也出栈，使得当前最小值变为当前最小值入栈之前的那个最小值。为了简单起见，可以在栈中保存int类型。

实现代码如下：

程序的运行结果为

算法性能分析：

这种方法申请了额外的一个栈空间来保存栈中最小的元素，从而达到了用O（1）的时间复杂度求栈中最小元素的目的，但是付出的代价是空间复杂度为O（N）。