O(1)取栈中最大值的思考

 

算法描述：

一个栈stack，具有push和pop操作，其时间复杂度皆为O(1)。

设计算法max操作，求栈中的最大值，该操作的时间复杂度也要求为O(1)。

可以修改栈的存储方式，push，pop的操作，但是要保证O(1)的时间复杂度，空间时间复杂度无要求。

(来源：http://www.iteye.com/topic/1116956 感谢分享)

 

思考：

增加一个最大值栈maxEleStack来存储原始栈stack的最大值。

定义一个变量，例如maxEle来保存当前最大值。

push操作：每次push一个元素进入栈stack的时候，该元素和maxEle比较，维护maxEle是最大元素，同时将maxEle push进最大值栈maxEleStack。

pop操作：从栈stack中pop一个元素出来的时候。最大值栈maxEleStack的顶上元素也同时被remove掉，同时维护maxEle 为最大值，即为已经remove完顶上元素后的栈maxEleStack中的最顶元素。

max操作，即取最大值，只需要取maxEleStack的顶上元素即可，所以时间复杂度是O(1)。