设计一个堆栈，使getMinimum（）应该为O（1）

Question

这是面试问题之一。您需要设计一个包含整数值的堆栈，以便getMinimum（）函数应返回堆栈中的最小元素。例如：考虑以下示例情况15->顶部1个462调用getMinimum（）时，它应返回1，这是最小元素 在堆栈中。 情况＃2stack.pop（）stack.pop（）注意：5和1都从堆栈中弹出。所以之后，堆栈看起来像，4->顶部62调用getMinimum（）时应返回2，这是 堆。食用者：getMinimum应该返回O（1）中的最小值设计时还必须考虑空间约束，如果您使用额外的空间，则它应该具有恒定的空间。

Answer 1

添加一个字段以保存最小值，并在Pop（）和Push（）期间对其进行更新。这样，getMinimum（）将为O（1），但是Pop（）和Push（）将不得不做更多的工作。

如果弹出最小值，则Pop（）将为O（n），否则它们仍将均为O（1）。调整大小时，根据Stack实现，Push（）变为O（n）。

这是一个快速实施

public sealed class MinStack {

    private int MinimumValue;

    private readonly Stack<int> Stack = new Stack<int>();

    public int GetMinimum() {

        if (IsEmpty) {

            throw new InvalidOperationException("Stack is empty");

        }

        return MinimumValue;

    }

    public int Pop() {

        var value = Stack.Pop();

        if (value == MinimumValue) {

            MinimumValue = Stack.Min();

        }

        return value;

    }

    public void Push(int value) {

        if (IsEmpty || value < MinimumValue) {

            MinimumValue = value;

        }

        Stack.Push(value);

    }

    private bool IsEmpty { get { return Stack.Count() == 0; } }

}