concevoir une pile telle que getMinimum( ) devrait être O(1)

Question

C'est une question d'entretien.

Vous devez concevoir une pile qui contient une valeur entière telle que getMinimum() doit retourner l'élément minimum de la pile.

Par exemple :

cas n° 1

5 TOP
1
4
6
2

Lorsque getMinimum() est appelé, il doit retourner 1, qui est l'élément minimum de la pile.

cas n° 2

stack.pop()
stack.pop()

Note : 5 et 1 sont sortis de la pile. Donc après cela, la pile ressemble à

4 TOP
6
2

Lorsque getMinimum() est appelé, il devrait retourner 2 qui est le minimum dans la pile.

Contraintes :

1. getMinimum devrait retourner la valeur minimale en O(1)
2. Les contraintes d'espace doivent également être prises en compte lors de la conception et si vous utilisez un espace supplémentaire, il doit être constant.

Answer 1

EDIT : Cela ne répond pas à la contrainte de "l'espace constant" - cela double essentiellement l'espace requis. Je doute fort qu'il existe une solution qui n'a pas Cependant, il n'est pas possible de faire cela sans modifier la complexité de l'exécution (par exemple, en rendant push/pop O(n)). Notez que cela ne change pas le complexité de l'espace requis, par exemple, si vous avez une pile avec O(n) d'espace requis, ce sera toujours O(n), mais avec un facteur constant différent.

Solution de l'espace non-constant

Gardez une pile "dupliquée" de "minimum de toutes les valeurs inférieures dans la pile". Quand vous sortez la pile principale, sortez aussi la pile minimale. Lorsque vous poussez la pile principale, poussez soit le nouvel élément, soit le minimum actuel, celui qui est le plus bas. getMinimum() est alors mis en œuvre comme juste minStack.peek() .

Donc en utilisant votre exemple, nous aurions :

Real stack        Min stack

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

Après avoir sauté deux fois, vous obtenez :

Real stack        Min stack

4                 2
6                 2
2                 2

Veuillez me faire savoir si ces informations ne sont pas suffisantes. C'est simple quand on le comprend, mais il faut parfois se creuser la tête au début :)

(L'inconvénient, bien sûr, est que cela double l'espace requis. Le temps d'exécution n'en souffre cependant pas de manière significative - c'est-à-dire que la complexité reste la même).

EDIT : Il existe une variante qui est légèrement plus compliquée, mais qui offre un meilleur espace en général. Nous avons toujours la pile min, mais nous ne sortons de celle-ci que lorsque la valeur que nous sortons de la pile principale est égale à celle de la pile min. Nous ne pousser à la pile principale lorsque la valeur poussée sur la pile principale est inférieure à ou égal à la valeur min actuelle. Cela permet de dupliquer les valeurs min. getMinimum() n'est toujours qu'une simple opération de lecture. Par exemple, en prenant la version originale et en poussant 1 à nouveau, on obtiendrait.. :

Real stack        Min stack

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

La sortie de la pile ci-dessus sort des deux piles parce que 1 == 1, ce qui laisse :

Real stack        Min stack

5  --> TOP        1
1                 2
4                 
6                 
2                 

Encore une fois sólo sort de la pile principale, car 5 > 1 :

Real stack        Min stack

1                 1
4                 2
6                 
2                 

Un nouvel éclatement fait éclater les deux piles car 1 == 1 :

Real stack        Min stack

4                 2
6                 
2                 

Cela aboutit à la même complexité d'espace dans le pire des cas (le double de la pile d'origine) mais à une bien meilleure utilisation de l'espace si nous obtenons rarement un "nouveau minimum ou égal".

EDIT : Voici une implémentation du plan diabolique de Pete. Je ne l'ai pas testé à fond, mais je pensez à c'est bon :)

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

Ajoutez un champ pour contenir la valeur minimale et mettez-le à jour pendant Pop() et Push(). De cette façon, getMinimum() sera O(1), mais Pop() et Push() devront faire un peu plus de travail.

Si la valeur minimale est "poppée", Pop() sera O(n), sinon ils seront toujours tous deux O(1). Lors du redimensionnement, Push() devient O(n) selon l'implémentation de la pile.

Voici une mise en œuvre rapide

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

}

Il stocke explicitement le minimum actuel, et si le minimum change, au lieu de pousser la valeur, il pousse une valeur de la même différence de l'autre côté du nouveau minimum ( si min = 7 et que vous poussez 5, il pousse 3 à la place ( 5-|7-5| = 3) et fixe min à 5 ; si vous poussez ensuite 3 quand min est 5, il voit que la valeur poussée est inférieure à min, donc inverse la procédure pour obtenir 7 pour le nouveau min, puis retourne le min précédent). Comme toute valeur qui ne modifie pas le minimum actuel est supérieure au minimum actuel, vous avez quelque chose qui peut être utilisé pour différencier les valeurs qui modifient le minimum et celles qui ne le font pas.

Dans les langages qui utilisent des entiers de taille fixe, vous empruntez un peu d'espace à la représentation des valeurs, de sorte qu'il peut y avoir un sous-débit et l'assertion échouera. Mais sinon, c'est un espace supplémentaire constant et toutes les opérations sont toujours O(1).

Les piles qui sont plutôt basées sur des listes liées ont d'autres endroits où vous pouvez emprunter un peu, par exemple en C le bit le moins significatif du prochain pointeur, ou en Java le type des objets dans la liste liée. Pour Java, cela signifie qu'il y a plus d'espace utilisé par rapport à une pile contiguë, car vous avez l'overhead des objets par lien :

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

En C, l'overhead n'existe pas, et vous pouvez emprunter le lsb du prochain pointeur :

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

Cependant, aucun de ces éléments n'est vraiment O(1). Elles ne nécessitent pas plus d'espace en pratique, car elles exploitent des trous dans les représentations des nombres, des objets ou des pointeurs dans ces langages. Mais une machine théorique qui utiliserait une représentation plus compacte nécessiterait l'ajout d'un bit supplémentaire à cette représentation dans chaque cas.

Answer 4

Eh bien, quelles sont les contraintes d'exécution de push y pop ? S'il n'est pas nécessaire qu'elles soient constantes, il suffit de calculer la valeur minimale dans ces deux opérations (en les rendant constantes). O ( n )). Sinon, je ne vois pas comment cela peut être fait avec un espace supplémentaire constant.

Answer 5

Voici mon code qui fonctionne avec O(1). Le code précédent que j'ai posté avait un problème lorsque l'élément minimum était retiré. J'ai modifié mon code. Celui-ci utilise une autre pile qui maintient l'élément minimum présent dans la pile au-dessus de l'élément courant poussé.

 class StackDemo
{
    int[] stk = new int[100];
    int top;
    public StackDemo()
    {
        top = -1;
    }
    public void Push(int value)
    {
        if (top == 100)
            Console.WriteLine("Stack Overflow");
        else
            stk[++top] = value;
    }
    public bool IsEmpty()
    {
        if (top == -1)
            return true;
        else
            return false;
    }
    public int Pop()
    {
        if (IsEmpty())
        {
            Console.WriteLine("Stack Underflow");
            return 0;
        }
        else
            return stk[top--];
    }
    public void Display()
    {
        for (int i = top; i >= 0; i--)
            Console.WriteLine(stk[i]);
    }
}
class MinStack : StackDemo
{
    int top;
    int[] stack = new int[100];
    StackDemo s1; int min;
    public MinStack()
    {
        top = -1;
        s1 = new StackDemo();
    }
    public void PushElement(int value)
    {
        s1.Push(value);
        if (top == 100)
            Console.WriteLine("Stack Overflow");
        if (top == -1)
        {
            stack[++top] = value;
            stack[++top] = value;   
        }
        else
        {
            //  stack[++top]=value;
            int ele = PopElement();
            stack[++top] = ele;
            int a = MininmumElement(min, value);
              stack[++top] = min;

                stack[++top] = value;
                stack[++top] = a;

        }
    }
    public int PopElement()
    {

        if (top == -1)
            return 1000;
        else
        {
            min = stack[top--];
            return stack[top--];
        }

    }
    public int PopfromStack()
    {
        if (top == -1)
            return 1000;
        else
        {
            s1.Pop();
            return PopElement();
        }
    }
    public int MininmumElement(int a,int b)
    {
        if (a > b)
            return b;
        else
            return a;
    }
    public int StackTop()
    {
        return stack[top];
    }
    public void DisplayMinStack()
    {
        for (int i = top; i >= 0; i--)
            Console.WriteLine(stack[i]);
    }
}
class Program
{
    static void Main(string[] args)
    {
        MinStack ms = new MinStack();
        ms.PushElement(15);
        ms.PushElement(2);
        ms.PushElement(1);
        ms.PushElement(13);
        ms.PushElement(5);
        ms.PushElement(21);
        Console.WriteLine("Min Stack");
        ms.DisplayMinStack();
        Console.WriteLine("Minimum Element:"+ms.StackTop());
        ms.PopfromStack();
        ms.PopfromStack();
        ms.PopfromStack();
        ms.PopfromStack();

        Console.WriteLine("Min Stack");
        ms.DisplayMinStack();
        Console.WriteLine("Minimum Element:" + ms.StackTop());
        Thread.Sleep(1000000);
    }
}