设计一个堆栈,使得getMinimum()应为O(1)

Question

这是一个面试问题.您需要设计一个包含整数值的堆栈,以便getMinimum()函数返回堆栈中的最小元素.

例如:考虑下面的例子

case #1

5  --> TOP
1
4
6
2

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

case #2

stack.pop()
stack.pop()

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

4  --> TOP
6
2

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

制约性:

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

Answer 1

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

非恒定空间解决方案

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

从两个堆栈弹出上面的pop,因为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;
    }
}

Answer 2

添加一个字段以保持最小值并在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; } }
}

Answer 3

public class StackWithMin {
    int min;
    int size;
    int[] data = new int[1024];

    public void push ( int val ) {
        if ( size == 0 ) {
            data[size] = val;
            min = val;
        } else if ( val < min) {
            data[size] = 2 * val - min;
            min = val;

            assert (data[size] < min); 
        } else {
            data[size] = val;
        }

        ++size;

        // check size and grow array
    }

    public int getMin () {
        return min;
    }

    public int pop () {
        --size;

        int val = data[size];

        if ( ( size > 0 ) && ( val < min ) ) {
            int prevMin = min;
            min += min - val;
            return prevMin;
        } else {
            return val;
        }
    }

    public boolean isEmpty () {
        return size == 0;
    }

    public static void main (String...args) {
        StackWithMin stack = new StackWithMin();

        for ( String arg: args ) 
            stack.push( Integer.parseInt( arg ) );

        while ( ! stack.isEmpty() ) {
            int min = stack.getMin();
            int val = stack.pop();

            System.out.println( val + " " + min );
        }

        System.out.println();
    }

}

它显式地存储当前最小值,如果最小值发生变化,而不是按下该值,则推送一个值与新最小值的另一侧相同的差值(如果min = 7而你按5,则按3而不是(5-) | 7-5 | = 3)并将min设置为5;如果你然后在min为5时弹出3它会看到弹出的值小于min,所以将程序反转为新的min得到7,然后返回上一个分钟).由于任何不会导致更改的值当前最小值都大于当前最小值,因此您可以使用某些值来区分更改最小值的值和不更改最小值的值.

在使用固定大小整数的语言中,您从值的表示中借用了一些空间,因此它可能会下溢并且断言将失败.但除此之外,它是恒定的额外空间,所有操作仍然是O(1).

基于链接列表的堆栈有其他可以借用的地方,例如在C中是下一个指针的最低有效位,或者在Java中是链接列表中对象的类型.对于Java而言,这意味着与连续堆栈相比,使用的空间更多,因为每个链接都有对象开销:

public class LinkedStackWithMin {
    private static class Link {
        final int value;
        final Link next;

        Link ( int value, Link next ) {
            this.value = value;
            this.next = next;
        }

        int pop ( LinkedStackWithMin stack ) {
            stack.top = next;
            return value;
        }
    }

    private static class MinLink extends Link {
        MinLink ( int value, Link next ) {
            super( value, next );
        }

        int pop ( LinkedStackWithMin stack ) {
            stack.top = next;
            int prevMin = stack.min;
            stack.min = value;
            return prevMin;
        }
    }

    Link top;
    int min;

    public LinkedStackWithMin () {
    }

    public void push ( int val ) {
        if ( ( top == null ) || ( val < min ) ) {
            top = new MinLink(min, top);
            min = val;
        } else {
            top = new Link(val, top);
        }
    }

    public int pop () {
        return top.pop(this);
    }

    public int getMin () {
        return min;
    }

    public boolean isEmpty () {
        return top == null;
    }

在C中,开销不存在,你可以借用下一个指针的lsb:

typedef struct _stack_link stack_with_min;

typedef struct _stack_link stack_link;

struct _stack_link {
    size_t  next;
    int     value;
};

stack_link* get_next ( stack_link* link ) 
{
    return ( stack_link * )( link -> next & ~ ( size_t ) 1 );
}

bool is_min ( stack_link* link )
{
    return ( link -> next & 1 ) ! = 0;
}

void push ( stack_with_min* stack, int value )
{
    stack_link *link = malloc ( sizeof( stack_link ) );

    link -> next = ( size_t ) stack -> next;

    if ( (stack -> next == 0) || ( value == stack -> value ) ) {
        link -> value = stack -> value;
        link -> next |= 1; // mark as min
    } else {
        link -> value = value;
    }

    stack -> next = link;
}

etc.;

但是,这些都不是真正的O(1).它们在实践中不需要更多空间,因为它们利用这些语言中数字,对象或指针的表示形式的漏洞.但是使用更紧凑的表示的理论机器将需要在每种情况下将额外的位添加到该表示.

Answer 4

我找到了一个满足所有提到的约束(恒定时间操作)和恒定额外空间的解决方案.

我们的想法是存储最小值和输入数之间的差异,如果最小值不再是最小值,则更新最小值.

代码如下:

public class MinStack {
    long min;
    Stack<Long> stack;

    public MinStack(){
        stack = new Stack<>();
    }

    public void push(int x) {
        if (stack.isEmpty()) {
            stack.push(0L);
            min = x;
        } else {
            stack.push(x - min); //Could be negative if min value needs to change
            if (x < min) min = x;
        }
    }

    public int pop() {
        if (stack.isEmpty()) return;

        long pop = stack.pop();

        if (pop < 0) {
            long ret = min
            min = min - pop; //If negative, increase the min value
            return (int)ret;
        }
        return (int)(pop + min);

    }

    public int top() {
        long top = stack.peek();
        if (top < 0) {
            return (int)min;
        } else {
           return (int)(top + min);
        }
    }

    public int getMin() {
        return (int)min;
    }
}

归功于:https://leetcode.com/discuss/15679/share-my-java-solution-with-only-one-stack

Answer 5

那么,什么是运行制约push和pop？如果它们不需要是常数,那么只需计算这两个操作中的最小值(使它们成为O(n)).否则,我不知道如何通过不断的额外空间来完成这项工作.