Min Stack

Q: Comment obtenir le minimum d’une pile en temps O(1) ?

Enregistrez le minimum au moment de l’empilement. Une pile ne change qu’à son sommet, donc le minimum des valeurs situées sous une hauteur donnée ne peut pas changer tant que cette hauteur est occupée. Gardez une deuxième pile contenant le minimum à chaque hauteur, ou uniquement chaque nouveau minimum, et getMin se réduit à la lecture de son sommet.

Q: Pourquoi empiler la valeur sur la pile des minimums lorsqu’elle est égale au minimum actuel ?

Parce que le minimum peut se trouver plusieurs fois dans la pile. Si tu n’enregistres que les valeurs strictement plus petites, deux occurrences de -2 partagent une entrée dans mins . Le premier dépilage de -2 supprime cette entrée, et getMin indique alors l’ancien minimum alors que le deuxième -2 est toujours présent. Enregistrer les valeurs égales donne à chaque occurrence sa propre entrée.

Q: Peut-on implémenter une pile Min avec un espace supplémentaire en O(1) ?

Oui, avec une pile et une variable min . Lorsque tu empiles un x inférieur au minimum actuel, stocke 2x - min à la place et définis min = x ; le nombre stocké est alors inférieur à min , ce qui le marque. Lorsqu’un nombre marqué est dépilé, le minimum précédent est 2 * min - stored . Le calcul dépasse les limites des entiers sur 32 bits, donc il faut utiliser des valeurs sur 64 bits, et la logique des signes est sujette aux erreurs ; la plupart des recruteurs sont satisfaits de la version à deux piles.

Q: Quelle est la complexité temporelle et spatiale de Min Stack ?

Chaque opération est en O(1) : push, pop, top et getMin ne lisent ou ne modifient que le sommet d’une ou deux piles. L’espace utilisé est en O(n) pour n valeurs stockées. Stocker le minimum à côté de chaque valeur utilise toujours 2n emplacements ; ne stocker que les nouveaux minimums en utilise entre n + 1 et 2n.

MoyenPile

+10

Conçois une pile qui, en plus des opérations habituelles push, pop et top, peut renvoyer la plus petite valeur qu’elle contient avec getMin. Chacune des quatre opérations doit s’exécuter en O(1).

Tu reçois les opérations dans l’ordre dans ops, avec args[i] contenant la valeur à empiler et 0 pour toutes les autres opérations. Exécute-les sur une seule pile initialement vide et renvoie une chaîne par opération : "null" pour push et pop, et le nombre sous forme de texte pour top et getMin.

Fonction

minStackOps(ops: string-array, args: integer-array) → string-array

opsstring-array: les opérations, dans l’ordre où elles s’exécutent
argsinteger-array: la valeur pour chaque opération push, 0 pour toutes les autres opérations
Renvoiestring-array: une réponse par opération, sous forme de texte

Contraintes

1 ≤ ops.length ≤ 3000
args.length == ops.length
Chaque ops[i] est push, pop, top ou getMin.
-2³¹+1 ≤ args[i] ≤ 2³¹-1 pour une opération d’ajout, et args[i] == 0 pour toute autre opération.
pop, top et getMin ne sont appelés que lorsque la pile contient au moins une valeur.

Exemples

Entrée: ops = ["push", "push", "push", "getMin", "pop", "top", "pop", "getMin"]args = [4, 1, 7, 0, 0, 0, 0, 0]
Sortie: ["null", "null", "null", "1", "null", "1", "null", "4"]
Explication: La pile contient 4, 1 et 7 du bas vers le haut, donc le plus petit est 1. Retirer 7 laisse 1 au sommet. Retirer aussi 1 ne laisse que 4, donc le minimum repasse à 4.

Entrée: ops = ["push", "push", "push", "getMin", "pop", "getMin", "pop", "getMin"]args = [3, -2, -2, 0, 0, 0, 0, 0]
Sortie: ["null", "null", "null", "-2", "null", "-2", "null", "3"]
Explication: Le minimum, -2, est empilé deux fois. Le premier dépilement supprime une copie et l'autre est toujours là, donc getMin reste à -2. Ce n'est qu'après le deuxième dépilement que le minimum revient à 3.

+16 tests cachés à la soumission

Pour aller plus loin

Peux-tu créer une file premier entré, premier sorti qui indique également son minimum en temps amorti O(1) ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Une pile classique effectue déjà push, pop et top en O(1) ; la difficulté consiste à conserver le minimum après les dépilements. Le point essentiel est qu’une pile ne change qu’à son sommet : tant qu’une valeur se trouve à une certaine hauteur, rien en dessous ne peut changer, donc le minimum de tous les éléments jusqu’à cette hauteur est fixe. Note ce minimum lors de l’empilement et un dépilement restaure gratuitement le minimum précédent. Les approches diffèrent par ce qu’elles notent.

Parcourez la pile à chaque appel de getMin

Intuition

Utilisez une pile ordinaire pour push, pop et top, et répondez à getMin en examinant chaque valeur qu’elle contient et en conservant la plus petite. C’est toujours correct, car cette méthode vérifie le contenu réel au moment de l’appel.

Cela ne respecte pas l’exigence O(1). Un appel à getMin sur une pile de n valeurs lit les n valeurs. Le test caché qui empile 1,500 valeurs en appelant getMin après chaque empilement lit environ 1,500 × 1,500 / 2, soit plus d’un million de valeurs, alors que les autres approches n’en lisent qu’une par appel. Un système exécutant 10^5 opérations de ce type en lirait des milliards.

Un minimum mis en cache ne résout pas le problème. Une variable contenant la plus petite valeur fonctionne pour les empilements, mais une fois cette valeur dépilée, impossible de connaître la suivante sans effectuer un nouveau parcours.

Algorithme

Stockez les valeurs dans une liste utilisée comme pile.
Pour push x, ajoutez x ; pour pop, supprimez la dernière valeur ; pour top, lisez-la.
Pour getMin, parcourez toutes les valeurs stockées et renvoyez la plus petite.
Enregistrez chaque réponse sous forme de texte et renvoyez la liste.

class MinStack:
    def __init__(self):
        self.values = []

    def push(self, x):
        self.values.append(x)

    def pop(self):
        self.values.pop()

    def top(self):
        return self.values[-1]

    def getMin(self):
        # Look at every stored value: O(n).
        smallest = self.values[0]
        for v in self.values:
            if v < smallest:
                smallest = v
        return smallest

def minStackOps(ops, args):
    stack = MinStack()
    result = []
    for op, arg in zip(ops, args):
        if op == "push":
            stack.push(arg)
            result.append("null")
        elif op == "pop":
            stack.pop()
            result.append("null")
        elif op == "top":
            result.append(str(stack.top()))
        else:
            result.append(str(stack.getMin()))
    return result

Stockez le minimum à côté de chaque valeur

Intuition

Tant qu’une valeur se trouve à la hauteur i de la pile, les valeurs en dessous ne peuvent pas changer ; la plus petite des i valeurs du bas reste donc fixe tant que cette valeur s’y trouve. Stocke ce nombre à côté de chaque valeur : une deuxième pile mins où mins[i] est la plus petite valeur de values[0..i].

Lors d’un empilement, la nouvelle entrée de mins est la plus petite valeur entre x et l’entrée située en dessous. Lors d’un dépilement, retire le sommet des deux piles ; le sommet de mins correspond à nouveau au minimum des valeurs restantes. getMin lit le sommet de mins.

Dans le premier exemple, les empilements de 4, 1 et 7 enregistrent les minimums 4, 1 et 1. Dépiler 7 laisse 1 au sommet de mins, et dépiler 1 laisse 4. Chaque opération ne touche qu’aux sommets des deux piles, donc chacune s’exécute en O(1). Le prix à payer est un deuxième nombre pour chaque valeur.

Algorithme

Gardez deux piles de même hauteur, values et mins.
Pour push x, empilez x sur values, puis empilez sur mins la plus petite valeur entre x et le sommet de mins (x lui-même si mins est vide).
Pour pop, dépilez les deux piles.
Pour top, lisez le sommet de values ; pour getMin, lisez le sommet de mins.
Enregistrez chaque réponse sous forme de texte et renvoyez la liste.

class MinStack:
    def __init__(self):
        self.values = []
        self.mins = []    # mins[i] is the smallest of values[0..i]

    def push(self, x):
        self.values.append(x)
        self.mins.append(x if not self.mins else min(x, self.mins[-1]))

    def pop(self):
        self.values.pop()
        self.mins.pop()

    def top(self):
        return self.values[-1]

    def getMin(self):
        return self.mins[-1]

def minStackOps(ops, args):
    stack = MinStack()
    result = []
    for op, arg in zip(ops, args):
        if op == "push":
            stack.push(arg)
            result.append("null")
        elif op == "pop":
            stack.pop()
            result.append("null")
        elif op == "top":
            result.append(str(stack.top()))
        else:
            result.append(str(stack.getMin()))
    return result

Une pile de minimums qui ne s’agrandit qu’à l’apparition d’un nouveau minimum

Intuition

Dans la deuxième approche, mins se répète souvent : empilez 1, puis 7, 8 et 9, et mins contient 1, 1, 1, 1. Une entrée répétée ne vous apprend rien de nouveau. Enregistrez donc une valeur dans mins uniquement lorsqu’elle devient le minimum, et supprimez-la lorsque cette même valeur quitte values.

Lors d’un empilement, ajoutez x à mins si mins est vide ou si x est inférieur ou égal à son sommet. Lors d’un dépilement, si la valeur qui quitte values est égale au sommet de mins, dépilez aussi mins. Le sommet de mins est toujours le minimum actuel : chaque valeur empilée après lui est soit plus grande, soit inférieure ou égale à lui, a donc aussi été enregistrée et a été dépilée depuis.

La comparaison doit être <=, et non <. Dans le deuxième exemple, -2 est empilé deux fois. Avec <, seule la première occurrence est enregistrée, le premier dépilement la supprime de mins, et getMin renvoie 3 alors qu’un -2 se trouve encore dans la pile. Avec <=, chaque occurrence a sa propre entrée.

Les quatre opérations restent en O(1). Lorsque les valeurs arrivent de la plus grande à la plus petite, mins atteint la même hauteur que values ; lorsque le minimum change rarement, il reste court.

Algorithme

Conserve une pile values et une pile mins.
Pour push x, empile x sur values. Si mins est vide ou si x est inférieur ou égal à son sommet, empile également x sur mins.
Pour pop, dépile values. Si la valeur retirée est égale au sommet de mins, dépile aussi mins.
Pour top, lis le sommet de values ; pour getMin, lis le sommet de mins.
Enregistre chaque réponse sous forme de texte et renvoie la liste.

class MinStack:
    def __init__(self):
        self.values = []
        self.mins = []    # each value that was a minimum when pushed; the top is the current minimum

    def push(self, x):
        self.values.append(x)
        # <= keeps one copy per equal minimum, so popping one leaves the others.
        if not self.mins or x <= self.mins[-1]:
            self.mins.append(x)

    def pop(self):
        if self.values.pop() == self.mins[-1]:
            self.mins.pop()

    def top(self):
        return self.values[-1]

    def getMin(self):
        return self.mins[-1]

def minStackOps(ops, args):
    stack = MinStack()
    result = []
    for op, arg in zip(ops, args):
        if op == "push":
            stack.push(arg)
            result.append("null")
        elif op == "pop":
            stack.pop()
            result.append("null")
        elif op == "top":
            result.append(str(stack.top()))
        else:
            result.append(str(stack.getMin()))
    return result

Pièges et cas limites

Les bugs concernent les copies du minimum et les éléments qu’un dépilement retire.

Enregistrer un nouveau minimum uniquement lorsque x est strictement plus petit. Une deuxième copie du minimum manque alors dans mins, et dépiler la première copie fait perdre le minimum alors que la deuxième est encore dans la pile. Le deuxième exemple met ce problème en évidence.
Conserver le minimum dans une seule variable. Cette méthode gère les empilements, mais après le dépilement du minimum, la variable contient une valeur obsolète, et trouver le suivant parmi les plus petits nécessite un parcours.
Comparer des entiers encapsulés par référence. En Java, Integer == Integer vérifie si les deux sont le même objet. C’est le cas pour les valeurs comprises entre -128 et 127, que Java met en cache, mais ce n’est pas le cas pour la plupart des valeurs plus grandes ; le contrôle du dépilement échoue donc uniquement pour les grandes valeurs. Convertis d’abord en int, comme le fait le code Java.
Dépiler mins à chaque dépilement dans la troisième approche. Cette pile ne diminue que lorsque la valeur retirée se trouve à son sommet ; dans la deuxième approche, les deux piles évoluent toujours ensemble.
Renvoyer un nombre pour pop. Dans ce format, pop renvoie "null", comme push.

Questions fréquentes4

Comment obtenir le minimum d’une pile en temps O(1) ?

Enregistrez le minimum au moment de l’empilement. Une pile ne change qu’à son sommet, donc le minimum des valeurs situées sous une hauteur donnée ne peut pas changer tant que cette hauteur est occupée. Gardez une deuxième pile contenant le minimum à chaque hauteur, ou uniquement chaque nouveau minimum, et getMin se réduit à la lecture de son sommet.

Pourquoi empiler la valeur sur la pile des minimums lorsqu’elle est égale au minimum actuel ?

Parce que le minimum peut se trouver plusieurs fois dans la pile. Si tu n’enregistres que les valeurs strictement plus petites, deux occurrences de -2 partagent une entrée dans mins. Le premier dépilage de -2 supprime cette entrée, et getMin indique alors l’ancien minimum alors que le deuxième -2 est toujours présent. Enregistrer les valeurs égales donne à chaque occurrence sa propre entrée.

Peut-on implémenter une pile Min avec un espace supplémentaire en O(1) ?

Oui, avec une pile et une variable min. Lorsque tu empiles un x inférieur au minimum actuel, stocke 2x - min à la place et définis min = x ; le nombre stocké est alors inférieur à min, ce qui le marque. Lorsqu’un nombre marqué est dépilé, le minimum précédent est 2 * min - stored. Le calcul dépasse les limites des entiers sur 32 bits, donc il faut utiliser des valeurs sur 64 bits, et la logique des signes est sujette aux erreurs ; la plupart des recruteurs sont satisfaits de la version à deux piles.

Quelle est la complexité temporelle et spatiale de Min Stack ?

Chaque opération est en O(1) : push, pop, top et getMin ne lisent ou ne modifient que le sommet d’une ou deux piles. L’espace utilisé est en O(n) pour n valeurs stockées. Stocker le minimum à côté de chaque valeur utilise toujours 2n emplacements ; ne stocker que les nouveaux minimums en utilise entre n + 1 et 2n.

Python

def minStackOps(ops, args):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

ops = ["push", "push", "push", "getMin", "pop", "top", "pop", "getMin"]
args = [4, 1, 7, 0, 0, 0, 0, 0]

Attendu

["null", "null", "null", "1", "null", "1", "null", "4"]

Min Stack

Fonction

Contraintes

Exemples

Indices

Solution

Parcourez la pile à chaque appel de getMin

Stockez le minimum à côté de chaque valeur

Une pile de minimums qui ne s’agrandit qu’à l’apparition d’un nouveau minimum

Pièges et cas limites

Questions fréquentes4

Problèmes similaires