如何设计一个堆栈,使getMinimum()应该是O(1)?

内容来源于 Stack Overflow,并遵循CC BY-SA 3.0许可协议进行翻译与使用

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

你需要设计一个包含整数值的堆栈,以便getMinimum()函数返回堆栈中的最小元素。

例如:考虑下面的例子

情况1

5  - > TOP
1
4
6
2

当调用getMinimum()时,它应该返回1,这是最小的元素 
在堆栈中。 

案例#2

stack.pop()
stack.pop()

注:5和1都从堆栈中移出。所以在这之后,堆栈
好像,

4  - > TOP
6
2

当getMinimum()被调用时应该返回2,这是最小的 
叠加。

制约性:

  1. getMinimum应返回O(1)中的最小值
  2. 设计时还必须考虑空间限制,如果使用额外的空间,它应该具有恒定的空间。
提问于
用户回答回答于

非恒定空间解决方案

保持“堆叠中所有值的最小值”的“重复”堆栈。当您弹出主堆栈时,也弹出最小堆栈。推动主堆叠时,按下新元素或当前最小值,以较低者为准。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

请让我知道这是不是足够的信息。当你练习它时很简单,但是最初可能需要一些头部划痕:)

有一个变化是稍微更繁琐,但总体上有更好的空间。我们仍然有最小堆栈,但是当我们从主堆栈弹出的值等于最小堆栈上的值时,我们只会弹出它。当推入主堆栈的值小于或等于当前最小值时,我们只推送最小堆栈。这允许重复最小值。例如,采取原始版本并再次按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;
    }
}
用户回答回答于

添加一个字段来保存最小值,并在Pop()和Push()期间更新它。这样,getMinimum()将是O(1),但是Pop()和Push()必须做更多的工作。

如果弹出最小值,则Pop()将为O(N),否则它们仍然都是O(1)。当调整大小时,Push()变成O(N),就像Stack实现那样。

下面是一个快速实现

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

扫码关注云+社区