## 如何设计一个堆栈，使getMinimum()应该是O(1)？内容来源于 Stack Overflow，并遵循CC BY-SA 3.0许可协议进行翻译与使用

• 回答 (2)
• 关注 (0)
• 查看 (45)

```情况1

5  - > TOP
1
4
6
2

stack.pop（）
stack.pop（）

4  - > TOP
6
2

```

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

### 2 个回答

``````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
``````

``````Real stack        Min stack

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

``````Real stack        Min stack

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

``````Real stack        Min stack

1                 1
4                 2
6
2
``````

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

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