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

难度系数：★★★☆☆　被考察系数：★★★★☆

分析与解答：

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

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

以栈{5，6，2}为例，实现代码如下：

程序的运行结果为

算法性能分析：

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