Pile à trouver min/trouver-max plus efficace que O(n)?

il s'agit d'une question classique sur les structures de données. L'intuition derrière le problème est la suivante - la seule façon que le maximum et le minimum peuvent changer est si vous poussez une nouvelle valeur sur la pile ou pop une nouvelle valeur hors de la pile. Cela étant, supposons qu'à chaque niveau de la pile, vous gardez une trace des valeurs maximale et minimale à ou au-dessous de ce point de la pile. Ensuite, lorsque vous poussez un nouvel élément sur la pile, vous pouvez facilement (en O(1) time) calculer la valeur maximale et minimale n'importe où dans la pile en comparant le nouvel élément que vous venez de pousser au maximum et au minimum actuels. De la même manière, lorsque vous désactivez un élément, vous exposez l'élément dans la pile un pas en dessous du sommet, qui a déjà les valeurs maximum et minimum dans le reste de la pile stockée à côté.

visuellement, supposons que nous ayons une pile et ajoutons les valeurs 2, 7, 1, 8, 3, et 9, dans cet ordre. On commence par en mettre 2, et on en met 2 sur la pile. Depuis le 2 est maintenant, la plus grande et la plus petite valeur dans la pile ainsi, nous enregistrons:

 2  (max 2, min 2)

maintenant, appuyez sur 7. Puisque 7 est supérieur à 2 (Le max actuel), nous nous retrouvons avec ceci:

 7  (max 7, min 2)
 2  (max 2, min 2)

Avis de ce droit maintenant, nous pouvons lire le max et le min de la pile en regardant le haut de la pile, et de voir que 7 est le max et 2 le min. Si nous poussons maintenant 1, nous obtenons

 1  (max 7, min 1)
 7  (max 7, min 2)
 2  (max 2, min 2)

ici, nous savons que 1 est le minimum, puisque nous pouvons comparer 1 à la valeur min mise en cache stock au sommet de la pile (2). Comme exercice, assurez-vous de comprendre pourquoi après avoir ajouté 8, 3 et 9, nous obtenons ceci:

 9  (max 9, min 1)
 3  (max 8, min 1)
 8  (max 8, min 1)
 1  (max 7, min 1)
 7  (max 7, min 2)
 2  (max 2, min 2)

maintenant, si nous voulons interroger le max et le min, nous pouvons le faire dans O(1) en lisant simplement le max stocké et le min atop la pile (9 et 1, respectivement).

maintenant, supposons que nous sortons l'élément supérieur. Cela donne 9 et modifie la pile pour être

 3  (max 8, min 1)
 8  (max 8, min 1)
 1  (max 7, min 1)
 7  (max 7, min 2)
 2  (max 2, min 2)

et maintenant noter que le max de ces éléments est 8, exactement la réponse correcte! Si on poussait alors 0, on obtiendrait ceci:

 0  (max 8, min 0)
 3  (max 8, min 1)
 8  (max 8, min 1)
 1  (max 7, min 1)
 7  (max 7, min 2)
 2  (max 2, min 2)

Et, comme vous pouvez le voir, le max et min sont calculées correctement.

dans l'ensemble, cela conduit à une implémentation de la pile qui a push O(1), pop, find-max, et find-min, qui est asymptotiquement aussi bonne qu'elle peut l'être. Je vais laisser l'implémentation comme un exercice. :-) Cependant, vous pouvez vous voulez envisager de mettre en œuvre la pile en utilisant l'une des techniques standard de mise en œuvre de la pile, comme l'utilisation d'un dynamic array ou liste liée d'objets, dont chacun détient l'élément de pile, min, et max. Vous pouvez le faire facilement en utilisant ArrayList ou LinkedList . Alternativement, vous pouvez utiliser la classe Java Stack fournie, bien que IIRC il a certains frais généraux en raison de la synchronisation qui pourrait être inutile pour cette application.

fait intéressant, une fois que vous avez construit une pile avec ces propriétés, Vous pouvez l'utiliser comme un bloc de construction pour construire une queue avec les mêmes propriétés et des garanties de temps. Vous pouvez également l'utiliser dans une construction plus complexe pour construire une file d'attente double avec ces propriétés ainsi.

Espérons que cette aide!

EDIT: si vous êtes curieux, j'ai C++ les implémentations de un min-pile et le fameux min-file d'attente sur mon site personnel. Espérons que cela montre à quoi cela pourrait ressembler dans la pratique!

bien que la réponse soit juste, mais nous pouvons faire mieux. Si la pile a beaucoup d'éléments, alors nous perdons beaucoup d'espace. Cependant, nous pouvons sauver cet espace inutile comme suit:

au lieu d'économiser la valeur min(ou max) avec chaque élément, nous pouvons utiliser deux piles. Parce que le changement de la valeur minimale(ou maximale) ne sera pas si fréquent, nous poussons la valeur min (ou max) à sa pile respective seulement quand la nouvelle valeur est <= (ou >= ) à la valeur courante min (ou max).

Voici la mise en œuvre dans Java :

public class StackWithMinMax extends Stack<Integer> {

    private Stack<Integer> minStack;
    private Stack<Integer> maxStack;

    public StackWithMinMax () {
        minStack = new Stack<Integer>();    
        maxStack = new Stack<Integer>();    
    }

    public void push(int value){
        if (value <= min()) { // Note the '=' sign here
            minStack.push(value);
        }

        if (value >= max()) {
            maxStack.push(value);
        }

        super.push(value);
    }

    public Integer pop() {
        int value = super.pop();

        if (value == min()) {
            minStack.pop();         
        }

        if (value == max()) {
            maxStack.pop();         
        }

        return value;
    }

    public int min() {
        if (minStack.isEmpty()) {
            return Integer.MAX_VALUE;
        } else {
            return minStack.peek();
        }
    }

    public int max() {
        if (maxStack.isEmpty()) {
            return Integer.MIN_VALUE;
        } else {
            return maxStack.peek();
        }
    }
}

notez qu'en utilisant cette approche, nous aurions très peu d'éléments dans minStack & maxStack , ce qui économiserait de l'espace. par exemple

Stack : MinStack : MaxStack

7         7         7
4         4         7
5         1         8 (TOP)
6         1 (TOP)         
7
8                 
1                  
1                  
7
2
4
2 (TOP)     

Peut-être trop tard pour répondre, mais juste pour le plaisir de l'enregistrement. Voici le code java.

import java.util.ArrayList;
import java.util.List;

public class MinStack {
    List<Node> items;

    public void push(int num) {
        if (items == null) {
            items = new ArrayList<Node>();
        }
        Node node = new Node(num);
        if (items.size() > 0) {
            node.min = Math.min(items.get(items.size() - 1).min, num);
            node.max = Math.max(items.get(items.size() - 1).max, num);

        } else {
            node.min = num;
            node.max = num;
        }
        items.add(node);
        printStack();
    }

    public Node pop() {
        Node popThis = null;
        if (items != null && items.size() > 0) {
            popThis = this.items.get(items.size() - 1);
            items.remove(items.size() - 1);         
        }
        printStack();
        return popThis;
    }

    public int getMin() {
        if (items != null && items.size() > 0) {
            int min = this.items.get(items.size() - 1).min;
            System.out.println("Minimum Element > " + min);
            return min;
        }
        return -1;
    }

    public int getMax() {
        if (items != null && items.size() > 0) {
            int max = this.items.get(items.size() - 1).max;
            System.out.println("Maximum Element > " + max);
            return max;
        }
        return -1;
    }

    public void printStack() {
        int i = 0;
        for (Node n : items) {
            System.out.print(n.data + " > ");
            if (i == items.size() - 1) {
                System.out.print(" | Min = " + n.min + " |");
                System.out.print(" | Max = " + n.max + " |");

            }
            i++;
        }
        System.out.println();
    }

    public static void main(String args[]) {
        MinStack stack = new MinStack();
        stack.push(10);

        stack.push(13);
        stack.push(19);
        stack.push(3);
        stack.push(2);
        stack.push(2);
        stack.printStack();
        stack.pop();
        //stack.getMin();
        stack.printStack();

    }
}

Classe De Pile:

class Node {

        int data;
        int min;
        int max;

        public Node(int data) {
            super();
            this.data = data;
        }

        public Node() {
            super();
        }
    }

À L'Aide De Linkedlist:

public class MaxMinStack {
    MaxMinLLNode headMin = null;
    MaxMinLLNode headMax = null;
    MaxMinLLNode tailMin = null;
    MaxMinLLNode tailMax = null;

    public void push(int data) {
        MaxMinLLNode node = new MaxMinLLNode(data, null);
        if (headMin == null) {
            headMin = node;
            tailMin = node;
        } else {
            if (data < headMin.data) {
                tailMin = headMin;
                headMin = node;
                node.nextNodeReference = tailMin;
            }
        }

        if (headMax == null) {
            headMax = node;
            tailMax = node;
        } else {
            if (data > headMax.data) {
                tailMax = headMax;
                headMax = node;
                node.nextNodeReference = tailMax;
            }
        }

    }

    public void pop() {
        System.out.println("Max Element:" + " " + String.valueOf(headMax.data));
        System.out.println("Min Element:" + " " + String.valueOf(headMin.data));
    }

    public void traverse() {
        MaxMinLLNode ptrMin = headMin;
        MaxMinLLNode ptrMax = headMax;
        System.out.println("Min");
        while (ptrMin != null) {
            System.out.println(ptrMin.data);
            ptrMin = ptrMin.nextNodeReference;
        }

        System.out.println("Max");
        while (ptrMax != null) {
            System.out.println(ptrMax.data);
            ptrMax = ptrMax.nextNodeReference;
        }

    }

    public static void main(String[] args) {
        MaxMinStack m = new MaxMinStack();
         m.push(7);
         m.push(4);
         m.push(5);
         m.push(6);
         m.push(7);
         m.push(8);
         m.push(1);
         m.push(1);
         m.push(7);
         m.push(2);
         m.push(4);
         m.push(2);
         m.traverse();
         m.pop();
    }

}

class MaxMinLLNode {
    int data;
    MaxMinLLNode nextNodeReference;

    MaxMinLLNode(int data, MaxMinLLNode node) {
        this.data = data;
        this.nextNodeReference = node;
    }
}