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

Question

Je suis intéressé par la création d'un Java structure de données similaire à une pile qui prend en charge les opérations suivantes de manière aussi efficace que possible:

• Pousser, ce qui ajoute un nouvel élément au sommet de la pile,
• Pop, ce qui supprime l'élément supérieur de la pile,
• Trouvez-Max, qui retourne (mais pas supprimer) le plus grand élément de la pile, et
• Trouvez-Min, qui retourne (mais pas supprimer) le plus petit élément de la pile, et

Quelle serait la manière la plus rapide de mise en œuvre de cette structure de données? Comment pourrais-je aller sur l'écriture en Java?

Answer 1

C'est un classique structures de données en question. L'intuition derrière le problème est comme suit: la seule façon que le maximum et le minimum pouvez changer si vous appuyez une nouvelle valeur dans la pile ou de la pop une nouvelle valeur hors de la pile. Compte tenu de cela, supposons qu'à chaque niveau de la pile-vous de garder les valeurs maximale et minimale au niveau ou en dessous de ce niveau dans la pile. Ensuite, lorsque vous appuyez sur un nouvel élément sur la pile, vous pouvez facilement (en O(1) fois) calculer la valeur maximale et la valeur minimale n'importe où dans la pile en comparant l'élément nouveau, vous avez juste poussée à l'actuelle, maximale et minimale. De même, lorsque vous enlevez un élément, vous permettra d'exposer l'élément dans la pile une étape au-dessous du sommet, qui a déjà les valeurs maximales et minimales dans le reste de la pile stockés à côté d'elle.

Visuellement, supposons que nous disposons d'une pile et d'ajouter les valeurs 2, 7, 1, 8, 3, et 9, dans cet ordre. On commence par pousser 2, et ainsi de nous pousser 2 sur notre stack. Depuis le 2 est maintenant la plus grande et la plus petite valeur dans la pile ainsi, nous enregistrons ce:

 2  (max 2, min 2)

Maintenant, nous allons pousser 7. Depuis le 7 est plus grand que 2 (le max), nous obtenons ceci:

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

Notez que pour l'instant, 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 avons maintenant pousser 1, on obtient

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

Ici, nous savons que 1 est le minimum, car on peut comparer 1 de la mise en cache min valeur stockée au sommet de la pile (2). Comme exercice, assurez-vous de comprendre pourquoi, après l'ajout de 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 en O(1) par la juste lecture de l'stockées max et min sur le sommet de la pile (9 et 1, respectivement).

Maintenant, supposons que nous avons de la pop l'élément supérieur. Cela donne 9 et modifie la pile à

 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, remarquez que le max de ces éléments est de 8, exactement la bonne réponse! Si nous avons ensuite poussé 0, nous aimerions obtenir 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, ce qui conduit à une mise en œuvre de la pile qui a O(1) push, pop, trouvez-max, et trouvez-min, qui est asymptotiquement aussi bon qu'il obtient. Je vais laisser la mise en œuvre d'un exercice. :-) Cependant, vous pouvez envisager la mise en œuvre de la pile à l'aide de l'un de la pile standard de mise en œuvre de techniques, comme l'utilisation d'un tableau dynamique ou une liste chaînée d'objets, chacun de qui détient l'élément de la pile, min et max. Vous pouvez le faire facilement en tirant profit de l' ArrayList ou LinkedList. Alternativement, vous pouvez utiliser le Java Stack classe, mais autant que je me souvienne il a des frais généraux en raison de la synchronisation qui est peut-ê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 file d'attente avec les mêmes propriétés et des garanties de temps. Vous pouvez également l'utiliser dans une construction plus complexe à construire un double clos de la file d'attente avec ces propriétés.

Espérons que cette aide!

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

Answer 2

Bien que la réponse est 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 de sauver min(ou max) valeur à chaque élément, nous pouvons utiliser deux piles. Parce que le changement dans le minimum(ou maximum) de la valeur ne sera pas si fréquent, on pousse le min(ou max) valeur à sa pile uniquement lorsque la nouvelle valeur est <=(ou >=) pour le courant min(ou max) de la valeur.

Ici est la mise en œuvre, en 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 que l'utilisation de cette approche, nous avons très peu d'éléments, en minStack & maxStack, économisant ainsi 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)