关于栈中最小元素O(1)

1.设计含min函数的栈,要求min、push和pop的时间复杂度都是o(1)。

  算法思想:需要设计一个辅助栈,用来存储当前栈中元素的最小值。网上有人说存储当前栈中元素的最小值的所在位置,虽然能节省空间,这其实是不对的,因为我在调用Min函数的时候,只能得到位置,还要对存储元素的栈不断的pop,才能得到最小值——时间复杂度o(1)。

  所以,还是在辅助栈中存储元素吧。

  此外,还要额外注意Push操作,第一个元素不用比较,自动成为最小值入栈。其它元素每次都要和栈顶元素比较,小的那个放到栈顶。

public class NewStack
{
    private Stack dataStack;
    private Stack mindataStack;
    public NewStack()
    {
        dataStack = new Stack();
        mindataStack = new Stack();
    }
    public void Push(int element)
    {
        dataStack.Push(element);
        if (mindataStack.Count == 0)
            mindataStack.Push(element);
        else if (element <= (int)mindataStack.Peek())
            mindataStack.Push(element);
        else //(element > mindataStack.Peek)
            mindataStack.Push(mindataStack.Peek());
    }
    
    public int Pop()
    {
        if (dataStack.Count == 0)
            throw new Exception("The stack is empty");
        
        mindataStack.Pop();
        return (int)dataStack.Pop();
    }
    public int Min()
    {
        if (dataStack.Count == 0)
            throw new Exception("The stack is empty");
        
        return (int)mindataStack.Peek();
    }
}

  2.设计含min函数的栈的另解

  话说,和青菜脸呆久了,就沾染了上海小市民意识,再加上原本我就很抠门儿,于是对于上一题目,我把一个栈当成两个用,就是说,每次push,先入站当前元素,然后入栈当前栈中最小元素;pop则每次弹出2个元素。

  算法代码如下所示(这里最小元素位于当前元素之上,为了下次比较方便):

public class NewStack
{
    private Stack stack;
    public NewStack()
    {
        stack = new Stack();
    }
    public void Push(int element)
    {
        if (stack.Count == 0)
        {
            stack.Push(element);
            stack.Push(element);
        }
        else if (element <= (int)stack.Peek())
        {
            stack.Push(element);
            stack.Push(element);
        }
        else //(element > stack.Peek)
        {
            object min = stack.Peek();
            stack.Push(element);
            stack.Push(min);            
        }
    }
    public int Pop()
    {
        if (stack.Count == 0)
            throw new Exception("The stack is empty");
        stack.Pop();
        return (int)stack.Pop();
    }
    public int Min()
    {
        if (stack.Count == 0)
            throw new Exception("The stack is empty");
        return (int)stack.Peek();
    }
}

  之所以说我这个算法比较叩门,是因为我只使用了一个栈,空间复杂度o(N),节省了一半的空间(算法1的空间复杂度o(2N))。

作者: typhoon85   发布时间: 2010-10-17