设计一个栈，使得 getMinimum() 应该是 O(1) [英] design a stack such that getMinimum( ) should be O(1)

问题描述

这是一道面试题.

您需要设计一个包含整数值的堆栈，以便 getMinimum() 函数应返回堆栈中的最小元素.

You need to design a stack which holds an integer value such that getMinimum() function should return the minimum element in the stack.

例如:

案例#1

5 ← TOP
1
4
6
2

5 ← TOP
1
4
6
2

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

When getMinimum() is called it should return 1, which is the minimum element in the stack.

案例#2

stack.pop()
stack.pop()

注意:5 和 1 都从堆栈中弹出.所以在此之后，堆栈看起来像

Note: Both 5 and 1 are popped out of the stack. So after this, the stack looks like

4 ← TOP
6
2

4 ← TOP
6
2

当 getMinimum() 被调用时，它应该返回 2，这是堆栈中的最小值.

When getMinimum() is called it should return 2 which is the minimum in the stack.

限制条件:

1. getMinimum 应该返回 O(1) 中的最小值
2. 在设计时也必须考虑空间限制，如果您使用额外的空间，它应该是恒定的空间.

推荐答案

这不符合恒定空间"约束 - 它基本上使所需空间加倍.我非常怀疑有一个解决方案不会这样做，但不会在某处破坏运行时的复杂性(例如，使 push/pop O(n)).请注意，这不会改变所需空间的复杂性，例如如果你有一个 O(n) 空间要求的堆栈，这仍然是 O(n) 只是具有不同的常数因子.

This fails the "constant space" constraint - it basically doubles the space required. I very much doubt that there's a solution which doesn't do that though, without wrecking the runtime complexity somewhere (e.g. making push/pop O(n)). Note that this doesn't change the complexity of the space required, e.g. if you've got a stack with O(n) space requirements, this will still be O(n) just with a different constant factor.

非常量空间解决方案

保留堆栈中所有较低值的最小值"的重复"堆栈.当您弹出主堆栈时，也弹出最小堆栈.推送主堆栈时，推送新元素或当前最小值，以较低者为准.getMinimum() 然后被实现为 minStack.peek().

Keep a "duplicate" stack of "minimum of all values lower in the stack". When you pop the main stack, pop the min stack too. When you push the main stack, push either the new element or the current min, whichever is lower. getMinimum() is then implemented as just minStack.peek().

因此，使用您的示例，我们将:

So using your example, we'd have:

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

如果这还不够信息，请告诉我.当你理解它时很简单，但一开始可能会有点头疼:)

Please let me know if this isn't enough information. It's simple when you grok it, but it might take a bit of head-scratching at first :)

(当然，它的缺点是它的空间需求翻了一番.虽然执行时间不会受到太大影响 - 即它仍然具有相同的复杂性.)

(The downside of course is that it doubles the space requirement. Execution time doesn't suffer significantly though - i.e. it's still the same complexity.)

有一个变体稍微有点繁琐，但总体上有更好的空间.我们仍然有最小堆栈，但只有当我们从主堆栈中弹出的值等于最小堆栈中的值时才从它弹出.当推入主堆栈的值小于或等于当前最小值时，我们只推到最小堆栈.这允许重复的最小值.getMinimum() 仍然只是一个窥视操作.例如，取原始版本并再次推送 1，我们将得到:

There's a variation which is slightly more fiddly, but has better space in general. We still have the min stack, but we only pop from it when the value we pop from the main stack is equal to the one on the min stack. We only push to the min stack when the value being pushed onto the main stack is less than or equal to the current min value. This allows duplicate min values. getMinimum() is still just a peek operation. For example, taking the original version and pushing 1 again, we'd get:

Real stack        Min stack

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

从上面弹出两个堆栈，因为 1 == 1，离开:

Popping from the above pops from both stacks because 1 == 1, leaving:

Real stack        Min stack

5  --> TOP        1
1                 2
4                 
6                 
2                 

再次弹出仅从主堆栈中弹出，因为 5 > 1:

Popping again only pops from the main stack, because 5 > 1:

Real stack        Min stack

1                 1
4                 2
6                 
2                 

再次弹出会弹出两个堆栈，因为 1 == 1:

Popping again pops both stacks because 1 == 1:

Real stack        Min stack

4                 2
6                 
2                 

如果我们很少得到新的最小值或相等"，这最终会产生相同的最坏情况空间复杂度(原始堆栈的两倍)但空间使用会更好.

This ends up with the same worst case space complexity (double the original stack) but much better space usage if we rarely get a "new minimum or equal".

这是皮特邪恶计划的一个实现.我还没有彻底测试过，但我认为没问题:)

Here's an implementation of Pete's evil scheme. I haven't tested it thoroughly, but I think it's okay :)

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

这篇关于设计一个栈，使得 getMinimum() 应该是 O(1)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！