Min Stack
Entwirf einen Stack, der neben den üblichen Operationen push, pop und top auch den kleinsten darin enthaltenen Wert mit getMin ausgeben kann. Jede der vier Operationen muss in O(1)-Zeit ausgeführt werden.
Du erhältst die Operationen der Reihe nach als ops, wobei args[i] den Wert für ein push und bei allen anderen Operationen 0 enthält. Führe sie auf einem Stack aus, der anfangs leer ist, und gib für jede Operation einen String zurück: "null" für push und pop sowie die Zahl als Text für top und getMin.
Funktion
- opsstring-array
- die Operationen in der Reihenfolge, in der sie ausgeführt werden
- argsinteger-array
- der Wert für jeden push, 0 für jede andere Operation
- Gibt zurückstring-array
- eine Antwort pro Operation, als Text
Einschränkungen
1 ≤ ops.length ≤ 3000args.length == ops.length- Jedes
ops[i]istpush,pop,topodergetMin. -231+1 ≤ args[i] ≤ 231-1für einen Push undargs[i] == 0für jede andere Operation.pop,topundgetMinwerden nur aufgerufen, wenn der Stack mindestens einen Wert enthält.
Beispiele
- Eingabe
- ops = ["push", "push", "push", "getMin", "pop", "top", "pop", "getMin"]args = [4, 1, 7, 0, 0, 0, 0, 0]
- Ausgabe
- ["null", "null", "null", "1", "null", "1", "null", "4"]
- Erklärung
- Der Stapel enthält von unten nach oben 4, 1 und 7, also ist 1 der kleinste Wert. Wenn 7 entfernt wird, liegt 1 oben. Wird auch 1 entfernt, bleibt nur 4 übrig, sodass das Minimum wieder 4 beträgt.
- Eingabe
- ops = ["push", "push", "push", "getMin", "pop", "getMin", "pop", "getMin"]args = [3, -2, -2, 0, 0, 0, 0, 0]
- Ausgabe
- ["null", "null", "null", "-2", "null", "-2", "null", "3"]
- Erklärung
- Das Minimum, -2, wird zweimal hinzugefügt. Beim ersten Entfernen wird eine Kopie entfernt, die andere ist noch vorhanden, daher bleibt
getMinbei -2. Erst nach dem zweiten Entfernen kehrt das Minimum zu 3 zurück.
- Eingabe
- ops = ["push", "push", "pop", "push", "getMin", "top"]args = [2, 0, 0, 8, 0, 0]
- Ausgabe
- ["null", "null", "null", "null", "2", "8"]
- Erklärung
- 0 wird wieder auf den Stapel gelegt und heruntergenommen, zählt also nicht mehr. Auf dem Stapel liegen dann 2 und 8: Oben liegt 8, und das Minimum ist 2.
+16 versteckte Tests beim Einreichen
Weiterführende Frage
Kannst du eine First-in-first-out-Warteschlange erstellen, die ihr Minimum auch in amortisierter O(1)-Zeit meldet?
Tipps
Öffne sie nacheinander. Jeder verrät ein bisschen mehr.
Eine Variable, die das Minimum enthält, funktioniert so lange, bis du dieses Minimum entfernst. Was müsstest du in diesem Moment wissen, und wann hättest du es aufschreiben können?
Ein Stapel ändert sich nur an seiner Spitze, daher bleibt der kleinste Wert unterhalb einer bestimmten Höhe gleich, solange diese Höhe belegt ist. Notiere das Minimum beim Hinzufügen eines Elements.
Führe neben den Werten einen zweiten Stack. Lege einen Wert darauf, wenn der neue Wert kleiner oder gleich seinem obersten Wert ist, und entferne den obersten Wert, wenn der Wert, der den Haupt-Stack verlässt, seinem obersten Wert entspricht. Sein oberster Wert ist dann immer die Antwort auf
getMin.
Lösung
Ein einfacher Stack führt push, pop und top bereits in O(1) aus; die Schwierigkeit ist ein Minimum, das Pops übersteht. Der entscheidende Umstand ist, dass sich ein Stack nur an seiner Spitze verändert: Solange ein Wert auf einer bestimmten Höhe liegt, kann sich darunter nichts ändern, daher bleibt das Minimum aller Werte bis zu dieser Höhe fest. Notiere dieses Minimum beim Push, und ein Pop stellt das vorherige kostenlos wieder her. Die Ansätze unterscheiden sich darin, was sie notieren.
Den Stack bei jedem getMin durchsuchen
Idee
Verwende für push, pop und top einen gewöhnlichen Stapel und beantworte getMin, indem du jeden darin gespeicherten Wert ansiehst und den kleinsten ermittelst. Das ist immer korrekt, weil dabei zum Zeitpunkt des Aufrufs der tatsächliche Inhalt geprüft wird.
Damit wird die O(1)-Anforderung verletzt. Ein Aufruf von getMin bei einem Stapel mit n Werten liest alle n Werte. Der versteckte Test, der 1.500 Werte auf den Stapel legt und nach jedem Push getMin aufruft, liest etwa 1.500 × 1.500 / 2, also über eine Million Werte, während die anderen Ansätze pro Aufruf einen Wert lesen. Ein System, das 10^5 solcher Operationen ausführt, würde Milliarden von Werten lesen.
Ein einzelner gespeicherter Minimalwert löst das Problem nicht. Eine Variable, die den kleinsten Wert enthält, funktioniert für Pushs, aber sobald dieser Wert vom Stapel entfernt wird, kannst du den nächstkleineren nicht ermitteln, ohne erneut alles zu durchsuchen.
Algorithmus
- Speichere die Werte in einer Liste, die als Stapel verwendet wird.
- Füge bei
push xxhinzu; entferne beipopden letzten Wert; lies ihn beitopaus. - Gehe bei
getMinalle gespeicherten Werte durch und gib den kleinsten zurück. - Halte jede Antwort als Text fest und gib die Liste zurück.
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 resultSpeichere das Minimum neben jedem Wert
Idee
mins, wobei mins[i] das kleinste Element von values[0..i] ist.
Beim Push ist der neue Eintrag in mins der kleinere Wert aus x und dem darunterliegenden Eintrag. Beim Pop entfernst du die obersten Elemente beider Stapel; das oberste Element von mins ist dann wieder das Minimum der verbleibenden Werte. getMin liest das oberste Element von mins.
Im ersten Beispiel speichern die Push-Operationen mit 4, 1 und 7 die Minima 4, 1 und 1. Beim Entfernen von 7 bleibt 1 oben auf mins, und beim Entfernen von 1 bleibt 4. Jede Operation greift nur auf die obersten Elemente zweier Stapel zu, daher dauert jede O(1). Der Preis dafür ist eine zweite Zahl für jeden Wert.
Algorithmus
- Halte zwei Stapel gleicher Höhe,
valuesundmins. - Bei
push xlegst duxaufvaluesund den kleineren Wert vonxund dem obersten Element vonminsaufmins(bei leeremminsxselbst). - Bei
popentfernst du das oberste Element aus beiden Stapeln. - Bei
topliest du das oberste Element vonvalues; beigetMinliest du das oberste Element vonmins. - Halte jede Antwort als Text fest und gib die Liste zurück.
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 resultEin Stapel von Minimumwerten, der nur bei einem neuen Minimum wächst
Idee
Beim zweiten Ansatz wiederholt sich mins oft: Füge 1 und dann 7, 8 und 9 hinzu, und mins enthält 1, 1, 1, 1. Ein wiederholter Eintrag sagt dir nichts Neues. Speichere einen Wert daher nur dann in mins, wenn er zum Minimum wird, und entferne ihn, wenn genau dieser Wert values verlässt.
Füge bei einem Push x zu mins hinzu, wenn mins leer ist oder x höchstens so groß wie der oberste Wert ist. Entferne bei einem Pop auch den obersten Wert aus mins, wenn der Wert, der values verlässt, dem obersten Wert von mins entspricht. Der oberste Wert von mins ist immer das aktuelle Minimum: Jeder danach hinzugefügte Wert ist entweder größer oder war höchstens so groß, wurde ebenfalls gespeichert und seitdem entfernt.
Der Vergleich muss <= sein, nicht <. Im zweiten Beispiel wird -2 zweimal hinzugefügt. Bei < wird nur die erste Kopie gespeichert, der erste Pop entfernt sie aus mins, und getMin gibt 3 zurück, obwohl noch ein -2 auf dem Stack liegt. Bei <= erhält jede Kopie ihren eigenen Eintrag.
Alle vier Operationen bleiben O(1). Wenn die Werte vom größten zum kleinsten eintreffen, wächst mins auf dieselbe Höhe wie values; wenn sich das Minimum nur selten ändert, bleibt mins kurz.
Algorithmus
- Führe einen Stapel
valuesund einen Stapelmins. - Bei
push xlegst duxaufvalues. Wennminsleer ist oderxhöchstens so groß wie sein oberstes Element ist, legst du auchxaufmins. - Bei
popentfernst du das oberste Element vonvalues. Wenn der entfernte Wert dem obersten Element vonminsentspricht, entfernst du auch das oberste Element vonmins. - Bei
topliest du das oberste Element vonvalues; beigetMinliest du das oberste Element vonmins. - Halte jede Antwort als Text fest und gib die Liste zurück.
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
Stolperfallen und Grenzfälle
Bei den Fehlern hier geht es um Kopien des Minimums und darum, was ein Pop-Vorgang entfernt.
- Ein neues Minimum nur aufzeichnen, wenn
xstrikt kleiner ist. Dann fehlt eine zweite Kopie des Minimums inmins, und beim Entfernen der ersten Kopie geht das Minimum verloren, obwohl die zweite noch auf dem Stack liegt. Das zweite Beispiel zeigt diesen Fehler. - Das Minimum in einer Variablen speichern. Das funktioniert beim Hinzufügen, aber nachdem das Minimum entfernt wurde, ist der Wert der Variablen veraltet, und um das nächstkleinere Element zu finden, muss der Stack durchsucht werden.
- Verpackte Ganzzahlen per Referenz vergleichen. In Java prüft
Integer == Integer, ob beide dasselbe Objekt sind. Das trifft zufällig auf Werte von -128 bis 127 zu, die Java zwischenspeichert, und schlägt bei den meisten größeren Werten fehl. Daher funktioniert die Pop-Prüfung nur bei großen Werten nicht. Wandle zuerst inintum, wie es der Java-Code tut. - Bei jedem Pop in der dritten Variante ein Element aus
minsentfernen. Der Stack wird nur verkleinert, wenn der entfernte Wert oben liegt; in der zweiten Variante bewegen sich die beiden Stacks immer gemeinsam. - Eine Zahl für
popzurückgeben. In diesem Format gibtpopwiepush"null"zurück.
Häufige Fragen4
Wie erhält man das Minimum eines Stacks in O(1)-Zeit?
Erfasse das Minimum zum Zeitpunkt des Einfügens. Ein Stack ändert sich nur an seiner Spitze, daher kann sich das Minimum der Werte unterhalb einer beliebigen Höhe nicht ändern, solange diese Höhe belegt ist. Führe einen zweiten Stack mit dem Minimum auf jeder Höhe oder nur mit jedem neuen Minimum, und getMin wird zu einem Lesen seiner Spitze.
Warum wird ein Wert auf den Min-Stack gelegt, wenn er dem aktuellen Minimum entspricht?
Weil das Minimum mehr als einmal auf dem Stack liegen kann. Wenn du nur strikt kleinere Werte aufzeichnest, teilen sich zwei Kopien von -2 einen Eintrag in mins. Beim ersten Entfernen von -2 wird dieser Eintrag gelöscht, und getMin meldet dann das alte Minimum, obwohl die zweite -2 noch vorhanden ist. Werden gleiche Werte aufgezeichnet, erhält jede Kopie ihren eigenen Eintrag.
Kann ein Min-Stack mit O(1) zusätzlichem Speicherplatz implementiert werden?
Ja, mit einem Stapel und einer Variablen min. Wenn du ein x unter dem aktuellen Minimum ablegst, speichere stattdessen 2x - min und setze min = x; die gespeicherte Zahl ist dann kleiner als min, wodurch sie markiert wird. Wenn eine markierte Zahl entfernt wird, ist das vorherige Minimum 2 * min - stored. Bei Werten nahe den Grenzwerten kommt es bei der Rechnung zu einem Überlauf bei 32-Bit-Ganzzahlen, daher sind 64-Bit-Werte erforderlich, und die Vorzeichenlogik ist fehleranfällig; die meisten Interviewer sind mit der Version mit zwei Stapeln zufrieden.
Wie hoch sind die Zeit- und Speicherkomplexität eines Min-Stacks?
Jede Operation ist O(1): push, pop, top und getMin lesen oder ändern jeweils nur die Spitze eines oder zweier Stapel. Der Speicherbedarf beträgt O(n) für n gespeicherte Werte. Das Speichern des Minimums neben jedem Wert benötigt immer 2n Plätze; das Speichern nur neuer Minima benötigt zwischen n + 1 und 2n.
Ähnliche Aufgaben
Aufgaben mit denselben Ideen. Wer zwei oder drei davon löst, behält das Muster.
Python
def minStackOps(ops, args):
# Schreibe hier den CodeFall 1
Fall 2
Fall 3
Eingabe
ops = ["push", "push", "push", "getMin", "pop", "top", "pop", "getMin"] args = [4, 1, 7, 0, 0, 0, 0, 0]
Erwartet
["null", "null", "null", "1", "null", "1", "null", "4"]