编辑：这失败了“恒定空间”约束-它基本上使所需的空间加倍。我非常怀疑是否有一种解决方案 不能
做到这一点，而不会破坏某个地方的运行时复杂性（例如，使push / pop O（n）成为可能）。请注意，这不会改变所需空间的 复杂性
，例如，如果您有一个具有O（n）空间要求的堆栈，那么这将是O（n），只是具有不同的常数因子。

非恒定空间解决方案

保持“重复的”堆栈，其中“堆栈中所有值的最小值都较低”。当您弹出主堆栈时，也要弹出最小堆栈。推入主堆栈时，推入新元素或当前最小值，以较低者为准。getMinimum()然后实现为just
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

如果这还不够，请告诉我。拖拉它很简单，但是一开始可能会有些头疼：)

（当然，缺点是它使空间需求增加了一倍。尽管执行时间并没有受到很大的影响-即它仍然是相同的复杂性。）

编辑：有一个变体，它稍微更有趣，但总体上具有更好的空间。我们仍然有最小堆栈，但是只有从主堆栈中弹出的值等于最小堆栈上的值时才从中弹出。仅当被压入主堆栈的值小于
或等于 当前最小值时，才 压入 最小堆栈。这允许重复的最小值。仍然只是一个窥视操作。例如，采用原始版本并再次按1，我们将得到：
__getMinimum()

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