设计一个栈使得 getMinimum( ) 应该是 O(1) [英] design a stack such that getMinimum( ) should be O(1)

问题描述

This is an interview question.

You need to design a stack which holds an integer value such that getMinimum() function should return the minimum element in the stack.

For example:

case #1

5 ← TOP
1
4
6
2

When getMinimum() is called it should return 1, which is the minimum element in the stack.

case #2

stack.pop()
stack.pop()

Note: Both 5 and 1 are popped out of the stack. So after this, the stack looks like

4 ← TOP
6
2

When getMinimum() is called it should return 2 which is the minimum in the stack.

Constraints:

1. getMinimum should return the minimum value in O(1)
2. Space constraint also has to be considered while designing it and if you use extra space, it should be of constant space.

解决方案

EDIT: This fails the "constant space" constraint - it basically doubles the space required. I very much doubt that there's a solution which doesn't do that though, without wrecking the runtime complexity somewhere (e.g. making push/pop O(n)). Note that this doesn't change the complexity of the space required, e.g. if you've got a stack with O(n) space requirements, this will still be O(n) just with a different constant factor.

Non-constant-space solution

Keep a "duplicate" stack of "minimum of all values lower in the stack". When you pop the main stack, pop the min stack too. When you push the main stack, push either the new element or the current min, whichever is lower. getMinimum() is then implemented as just minStack.peek().

So using your example, we'd have:

Real stack        Min stack

5  --> TOP        1
1                 1
4                 2
6                 2
2                 2

After popping twice you get:

Real stack        Min stack

4                 2
6                 2
2                 2

Please let me know if this isn't enough information. It's simple when you grok it, but it might take a bit of head-scratching at first :)

(The downside of course is that it doubles the space requirement. Execution time doesn't suffer significantly though - i.e. it's still the same complexity.)

EDIT: There's a variation which is slightly more fiddly, but has better space in general. We still have the min stack, but we only pop from it when the value we pop from the main stack is equal to the one on the min stack. We only push to the min stack when the value being pushed onto the main stack is less than or equal to the current min value. This allows duplicate min values. getMinimum() is still just a peek operation. For example, taking the original version and pushing 1 again, we'd get:

Real stack        Min stack

1  --> TOP        1
5                 1
1                 2
4                 
6                 
2                 

Popping from the above pops from both stacks because 1 == 1, leaving:

Real stack        Min stack

5  --> TOP        1
1                 2
4                 
6                 
2                 

Popping again only pops from the main stack, because 5 > 1:

Real stack        Min stack

1                 1
4                 2
6                 
2                 

Popping again pops both stacks because 1 == 1:

Real stack        Min stack

4                 2
6                 
2                 

This ends up with the same worst case space complexity (double the original stack) but much better space usage if we rarely get a "new minimum or equal".

EDIT: Here's an implementation of Pete's evil scheme. I haven't tested it thoroughly, but I think it's okay :)

using System.Collections.Generic;

public class FastMinStack<T>
{
    private readonly Stack<T> stack = new Stack<T>();
    // Could pass this in to the constructor
    private readonly IComparer<T> comparer = Comparer<T>.Default;

    private T currentMin;

    public T Minimum
    {
        get { return currentMin; }
    }

    public void Push(T element)
    {
        if (stack.Count == 0 ||
            comparer.Compare(element, currentMin) <= 0)
        {
            stack.Push(currentMin);
            stack.Push(element);
            currentMin = element;
        }
        else
        {
            stack.Push(element);
        }
    }

    public T Pop()
    {
        T ret = stack.Pop();
        if (comparer.Compare(ret, currentMin) == 0)
        {
            currentMin = stack.Pop();
        }
        return ret;
    }
}

这篇关于设计一个栈使得 getMinimum( ) 应该是 O(1)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！