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

问题描述

这是面试问题之一。您需要设计一个包含整数值的堆栈，以便getMinimum（）函数应该返回堆栈中的最小元素。

This is one of 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: consider the below 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 poped out of the stack. So after this, the stack
looks like,

4  --> TOP
6
2

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

Constriants：

1. getMinimum应返回O（1）中的最小值


2. 空间约束在设计时也必须考虑，如果使用额外的空间，应该是

推荐答案

编辑：这会导致恒定空间的约束 - 它基本上加倍所需空间我非常怀疑有一个解决方案，虽然没有破坏运行时的复杂性（例如使用push / pop O（n）），但是这样做并不是这样的。请注意，这不会改变所需空间的复杂性。如果你有一个O（n）空间要求的堆栈，这仍然是O（n），只有不同的常数因子。

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.

恒定空间解决方案

保留堆栈中所有值的最小值的重复堆栈。当您弹出主堆栈时，也弹出最小堆栈。当您按下主堆栈时，按下新元素或当前最小值（以较低者为准）。 getMinimum（）然后实现为 minStack.peek（）。

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.)

编辑：有一个比较简单的变体，但总体上有更好的空间。我们仍然有最小的堆栈，但是当我们从主堆栈弹出的值等于最小堆栈中的值时，我们只从其中弹出。当推送到主堆栈的值小于或等于到当前最小值时，我们只将 推送到最小堆栈。这允许重复的最小值。 getMinimum（）仍然只是一个偷看操作。例如，使用原始版本并再次按1，我们将得到：

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                 

从上述两个堆栈弹出，因为1 == 1，留下：

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

Real stack        Min stack

5  --> TOP        1
1                 2
4                 
6                 
2                 

<因为5> 1：

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

Real stack        Min stack

1                 1
4                 2
6                 
2                 

再次弹出Popping会弹出两个堆栈，因为1 == 1：

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".

编辑：这是Pete的邪恶方案。我没有彻底测试，但我认为可以：）

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屋！