Tuesday, February 24, 2009

stack min()

对栈数据结构进行改进,加一个 min() 功能,使之能在常数 (即 O(1)) 时间内给出栈中的最小值。可对 push() 和 pop() 函数进行修改,但要求其时间复杂度都只能是 O(1)。

思路:
1. 设置一个主栈,一个辅栈,辅栈用于存储当前栈中最小值元素。
push:
如果主栈为空,push 进主栈和辅栈; 如果主栈非空,push 进主栈,然后把这个数跟辅栈的栈顶元素比较,把较小值 push 进辅栈;
pop:
辅栈 pop 一次,主栈 pop 一次并返回;
min:
返回辅栈栈顶元素即可。
2. 在栈元素中扩展出最小值域,栈顶元素的最小值域中保持当前栈中的最小值。
与 1 基本一样,不用辅助栈,但要修改栈内元素结构。
3. 设置一个主栈,一个辅栈,辅栈用于存储主栈中当前最小值元素及其到主栈底的距离。
push:
push 进主栈。当主栈新栈顶元素比辅栈的栈顶元素更小时,把主栈的新栈顶数据和主栈当前栈大小压入辅栈。
pop:
如果主栈 pop 后,其栈大小比辅栈栈顶元素的距离小,则辅栈的栈顶也弹出。
min:
返回辅栈的栈顶元素即可。
基本思想跟 1 一样,但在主栈中重复元素较多,或者排好序的数据按升序入栈的情况下,可以节省空间。但如果栈中没有重复元素,且排好序的数据按降序入栈,则需要更多空间。

注:如果要求最大值,同理可得

No comments: