algorithm - 设计一个堆栈使得 getMinimum( ) 应该是 O(1)

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.

约束:

1. getMinimum 应该在 O(1) 中返回最小值
2. 在设计时还必须考虑空间限制，如果您使用额外的空间，它应该是恒定的空间。

Answer 1

编辑:这不符合“恒定空间”约束——它基本上使所需空间翻倍。我非常怀疑是否有一种解决方案不会这样做，但不会破坏某处的运行时复杂性(例如，使 push/pop O(n))。请注意，这不会改变所需空间的复杂性，例如如果你有一个 O(n) 空间要求的堆栈，这仍然是 O(n) 只是具有不同的常数因子。

非恒定空间解

保留“堆栈中所有较低值的最小值”的“重复”堆栈。弹出主堆栈时，也弹出最小堆栈。当您压入主堆栈时，压入新元素或当前最小值，以较低者为准。 getMinimum() 然后作为 minStack.peek() 实现。

因此使用您的示例，我们将:

Real stack        Min stack

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

弹出两次后你得到:

Real stack        Min stack

4                 2
6                 2
2                 2

如果这些信息还不够，请告诉我。当你理解它时它很简单，但一开始可能会让人头疼 :)

(当然，它的缺点是它使空间需求加倍。执行时间并没有受到显着影响 - 即它仍然是相同的复杂性。)

编辑:有一种变体稍微复杂一些，但总体上空间更大。我们仍然有最小堆栈，但只有当我们从主堆栈中弹出的值等于最小堆栈中的值时，我们才会从中弹出。当被插入主堆栈的值小于或等于当前最小值时，我们只会推到最小堆栈。这允许重复的最小值。 getMinimum() 仍然只是一个窥视操作。例如，将原始版本再次压入 1，我们将得到:

Real stack        Min stack

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

因为 1 == 1，所以从上面的栈中弹出:

Real stack        Min stack

5  --> TOP        1
1                 2
4                 
6                 
2                 

再次弹出 仅 从主堆栈弹出，因为 5 > 1:

Real stack        Min stack

1                 1
4                 2
6                 
2                 

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

Real stack        Min stack

4                 2
6                 
2                 

如果我们很少得到“新的最小值或相等值”，这将以相同的最坏情况空间复杂度(原始堆栈的两倍)结束，但空间使用率要好得多。

编辑:这是皮特邪恶计划的实现。我还没有彻底测试过，但我认为没问题:)

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;
    }
}