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

Question

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

例如：考虑以下示例

情况1

5->顶部

1个

4

6

2

调用getMinimum（）时，它应返回1，这是最小元素 

在堆栈中。 

情况＃2

stack.pop（）

stack.pop（）

注意：5和1都从堆栈中弹出。所以之后，堆栈

看起来像，

4->顶部

6

2

调用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 {&nbsp; &nbsp; private int MinimumValue;&nbsp; &nbsp; private readonly Stack<int> Stack = new Stack<int>();&nbsp; &nbsp; public int GetMinimum() {&nbsp; &nbsp; &nbsp; &nbsp; if (IsEmpty) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; throw new InvalidOperationException("Stack is empty");&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; return MinimumValue;&nbsp; &nbsp; }&nbsp; &nbsp; public int Pop() {&nbsp; &nbsp; &nbsp; &nbsp; var value = Stack.Pop();&nbsp; &nbsp; &nbsp; &nbsp; if (value == MinimumValue) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; MinimumValue = Stack.Min();&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; return value;&nbsp; &nbsp; }&nbsp; &nbsp; public void Push(int value) {&nbsp; &nbsp; &nbsp; &nbsp; if (IsEmpty || value < MinimumValue) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; MinimumValue = value;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; Stack.Push(value);&nbsp; &nbsp; }&nbsp; &nbsp; private bool IsEmpty { get { return Stack.Count() == 0; } }}