BEARBEITEN: Dadurch wird die Einschränkung "konstanter Speicherplatz" nicht erfüllt - der erforderliche Speicherplatz wird grundsätzlich verdoppelt. Ich bezweifle sehr, dass es eine Lösung gibt, die dies jedoch nicht tut, ohne die Laufzeitkomplexität irgendwo zu zerstören (z. B. Push / Pop O (n)). Beachten Sie, dass dies die Komplexität des erforderlichen Speicherplatzes nicht ändert. Wenn Sie beispielsweise einen Stapel mit O (n) Speicherplatzbedarf haben, ist dies immer noch O (n), nur mit einem anderen konstanten Faktor.
Nicht konstante Raumlösung
Halten Sie einen "doppelten" Stapel von "Minimum aller Werte niedriger im Stapel". Wenn Sie den Hauptstapel platzen lassen, platzen Sie auch den Min-Stapel. Wenn Sie den Hauptstapel drücken, drücken Sie entweder das neue Element oder die aktuelle min, je nachdem, welcher Wert niedriger ist. getMinimum()
wird dann als gerecht implementiert minStack.peek()
.
Anhand Ihres Beispiels hätten wir also:
Real stack Min stack
5 --> TOP 1
1 1
4 2
6 2
2 2
Nach zweimaligem Poppen erhalten Sie:
Real stack Min stack
4 2
6 2
2 2
Bitte lassen Sie mich wissen, wenn dies nicht genug Informationen sind. Es ist einfach, wenn du es grokst, aber es könnte zuerst ein bisschen Kopfkratzen erfordern :)
(Der Nachteil ist natürlich, dass sich der Platzbedarf verdoppelt. Die Ausführungszeit leidet jedoch nicht wesentlich - dh sie ist immer noch gleich komplex.)
EDIT: Es gibt eine Variante, die etwas fummeliger ist, aber im Allgemeinen einen besseren Platz bietet. Wir haben immer noch den Min-Stack, aber wir öffnen ihn nur, wenn der Wert, den wir vom Hauptstapel entfernen, dem auf dem Min-Stack entspricht. Wir pushen nur auf den Min-Stapel, wenn der Wert, der auf den Hauptstapel verschoben wird, kleiner oder gleich dem aktuellen Min-Wert ist. Dies ermöglicht doppelte Mindestwerte. getMinimum()
ist immer noch nur eine Peek-Operation. Wenn wir zum Beispiel die Originalversion nehmen und erneut 1 drücken, erhalten wir:
Real stack Min stack
1 --> TOP 1
5 1
1 2
4
6
2
Das Knallen von oben taucht von beiden Stapeln auf, weil 1 == 1, so dass:
Real stack Min stack
5 --> TOP 1
1 2
4
6
2
Das erneute Poppen wird nur vom Hauptstapel entfernt, da 5> 1:
Real stack Min stack
1 1
4 2
6
2
Beim erneuten Poppen werden beide Stapel angezeigt, da 1 == 1:
Real stack Min stack
4 2
6
2
Dies führt zu der gleichen Speicherplatzkomplexität im ungünstigsten Fall (doppelt so viel wie der ursprüngliche Stapel), aber zu einer viel besseren Speicherplatznutzung, wenn wir selten ein "neues Minimum oder gleich" erhalten.
EDIT: Hier ist eine Implementierung von Petes bösem Schema. Ich habe es nicht gründlich getestet, aber ich denke es ist okay :)
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;
}
}
Fügen Sie ein Feld hinzu, das den Mindestwert enthält, und aktualisieren Sie es während Pop () und Push (). Auf diese Weise wird getMinimum () O (1) sein, aber Pop () und Push () müssen etwas mehr Arbeit leisten.
Wenn der Mindestwert angezeigt wird, ist Pop () O (n), andernfalls sind beide immer noch O (1). Beim Ändern der Größe wird Push () gemäß der Stack-Implementierung zu O (n).
Hier ist eine schnelle Implementierung
quelle
Es speichert das aktuelle Minimum explizit und wenn sich das Minimum ändert, drückt es anstelle des Werts einen Wert mit der gleichen Differenz auf die andere Seite des neuen Minimums (wenn min = 7 und Sie 5 drücken, drückt es stattdessen 3 (5-)) | 7-5 | = 3) und setzt min auf 5; wenn Sie dann 3 platzen lassen, wenn min 5 ist, wird angezeigt, dass der Pop-Wert kleiner als min ist. Kehren Sie daher die Prozedur um, um 7 für das neue min zu erhalten, und geben Sie das vorherige zurück Mindest). Da jeder Wert, der keine Änderung verursacht, das aktuelle Minimum größer als das aktuelle Minimum ist, können Sie zwischen Werten, die das Minimum ändern, und Werten, die dies nicht tun, unterscheiden.
In Sprachen, in denen Ganzzahlen mit fester Größe verwendet werden, leihen Sie sich etwas Speicherplatz aus der Darstellung der Werte aus, sodass diese möglicherweise unterlaufen und die Bestätigung fehlschlägt. Ansonsten ist es ein konstanter zusätzlicher Speicherplatz und alle Operationen sind immer noch O (1).
Stapel, die stattdessen auf verknüpften Listen basieren, haben andere Stellen, von denen Sie ein bisschen ausleihen können, z. B. in C das niedrigstwertige Bit des nächsten Zeigers oder in Java den Typ der Objekte in der verknüpften Liste. Für Java bedeutet dies, dass im Vergleich zu einem zusammenhängenden Stapel mehr Speicherplatz verwendet wird, da Sie den Objekt-Overhead pro Link haben:
In C ist der Overhead nicht vorhanden, und Sie können das lsb des nächsten Zeigers ausleihen:
Keines davon ist jedoch wirklich O (1). In der Praxis benötigen sie keinen Platz mehr, da sie Lücken in der Darstellung von Zahlen, Objekten oder Zeigern in diesen Sprachen ausnutzen. Eine theoretische Maschine, die eine kompaktere Darstellung verwendet, würde jedoch erfordern, dass dieser Darstellung jeweils ein zusätzliches Bit hinzugefügt wird.
quelle
pop()
wenn der letzteInteger.MIN_VALUE
Push- Wert war (z. B. Push 1, Push Integer.MIN_VALUE, Pop). Dies ist auf den oben erwähnten Unterlauf zurückzuführen. Andernfalls funktioniert für alle ganzzahligen Werte.Ich habe eine Lösung gefunden, die alle genannten Einschränkungen (Operationen mit konstanter Zeit) und konstantem zusätzlichen Platz erfüllt .
Die Idee ist, die Differenz zwischen dem Min-Wert und der Eingangsnummer zu speichern und den Min-Wert zu aktualisieren, wenn er nicht mehr das Minimum ist.
Der Code lautet wie folgt:
Das Guthaben geht an: https://leetcode.com/discuss/15679/share-my-java-solution-with-only-one-stack
quelle
Nun, was sind die Laufzeitbeschränkungen von
push
undpop
? Wenn sie nicht konstant sein müssen, berechnen Sie einfach den Mindestwert in diesen beiden Operationen (machen Sie sie zu O ( n )). Ansonsten sehe ich nicht, wie dies mit konstantem zusätzlichen Platz gemacht werden kann.quelle
Hier ist mein Code, der mit O (1) läuft. Der vorherige Code, den ich gepostet habe, hatte ein Problem, als das minimale Element platzte. Ich habe meinen Code geändert. Dieser verwendet einen anderen Stapel, der das im Stapel vorhandene Mindestelement über dem aktuell geschobenen Element beibehält.
quelle
Ich habe eine andere Art von Stapel verwendet. Hier ist die Implementierung.
Ausgabe:
Versuch es. Ich denke, es beantwortet die Frage. Das zweite Element jedes Paares gibt den Mindestwert an, der beim Einfügen dieses Elements angezeigt wurde.
quelle
Ich poste hier den vollständigen Code, um Min und Max in einem bestimmten Stapel zu finden.
Die zeitliche Komplexität beträgt O (1).
Lassen Sie mich wissen, wenn Sie vor einem Problem stehen
Danke, Vikash
quelle
Sie können Ihre ursprüngliche Stapelklasse erweitern und einfach das Min-Tracking hinzufügen. Lassen Sie die ursprüngliche übergeordnete Klasse alles andere wie gewohnt behandeln.
quelle
Hier ist meine Lösung in Java mit Likes-Liste.
}}
quelle
Nehmen wir an, der Stapel, an dem wir arbeiten werden, ist folgender:
In der obigen Darstellung wird der Stapel nur durch den linken Wert erstellt. Der [Minimalwert] des rechten Werts wird nur zu Illustrationszwecken geschrieben, die in einer Variablen gespeichert werden.
Das eigentliche Problem ist, wenn der Wert, der der Minimalwert ist, an diesem Punkt entfernt wird. Wie können wir wissen, was das nächste minimale Element ist, ohne über den Stapel zu iterieren?
Wie zum Beispiel in unserem Stapel, wenn 6 get's platzen, wissen wir, dass dies nicht das minimale Element ist, da das minimale Element 2 ist, sodass wir dies sicher entfernen können, ohne unseren minimalen Wert zu aktualisieren.
Aber wenn wir 2 platzen lassen, können wir sehen, dass der Mindestwert gerade 2 ist. Wenn dieser Wert herausspringt, müssen wir den Mindestwert auf 3 aktualisieren.
Punkt 1:
Wenn Sie nun genau beobachten, müssen wir aus diesem bestimmten Zustand einen Minimalwert = 3 erzeugen [2, Minuswert = 2]. oder wenn Sie den Stapel depperinieren, müssen wir aus diesem bestimmten Zustand minvalue = 7 generieren [3, minvalue = 3], oder wenn Sie im Stapel depper werden, müssen wir aus diesem bestimmten Zustand minvalue = 8 generieren [7, minvalue = 7]
Haben Sie in allen drei oben genannten Fällen etwas gemeinsam bemerkt? Der Wert, den wir generieren müssen, hängt von zwei Variablen ab, die beide gleich sind. Richtig. Warum passiert das, weil wir, wenn wir ein Element verschieben, das kleiner als der aktuelle Minimalwert ist, dieses Element im Grunde genommen in den Stapel verschieben und dieselbe Zahl auch im Minimalwert aktualisieren.
Punkt 2:
Wir speichern also im Grunde ein Duplikat derselben Nummer einmal im Stapel und einmal in der Variablen minvalue. Wir müssen uns darauf konzentrieren, diese Duplizierung zu vermeiden und nützliche Daten im Stapel oder im Minimalwert zu speichern, um das vorherige Minimum zu generieren, wie in den obigen FÄLLEN gezeigt.
Konzentrieren wir uns darauf, was im Stapel gespeichert werden soll, wenn der in Push zu speichernde Wert kleiner als der Mindestwert ist. Nennen wir diese Variable y, also sieht unser Stapel jetzt ungefähr so aus:
Ich habe sie in y1, y2, y3 umbenannt, um Verwirrung zu vermeiden, dass alle den gleichen Wert haben.
Punkt 3:
Versuchen wir nun, einige Einschränkungen über y1, y2 und y3 zu finden. Erinnern Sie sich, wann genau wir den Minimalwert aktualisieren müssen, während Sie pop () ausführen, nur wenn wir das Element gepoppt haben, das dem Minimalwert entspricht? Wenn wir etwas Größeres als den Mindestwert anzeigen, müssen wir den Mindestwert nicht aktualisieren. Um die Aktualisierung des Min-Werts auszulösen, sollten y1, y2 und y3 kleiner sein als der entsprechende Min-Wert.
Kommen wir nun zurück, um y zu füllen. Wir müssen einen Wert generieren und y zum Zeitpunkt des Pushs setzen. Denken Sie daran. Nehmen wir den Wert, der für Push kommt, als x, was kleiner als der prevMinvalue ist, und den Wert, den wir tatsächlich im Stapel pushen, als y. Eines ist also offensichtlich: newMinValue = x und y <newMinvalue.
Jetzt müssen wir y mit Hilfe von prevMinvalue und x (newMinvalue) berechnen (denken Sie daran, dass y eine beliebige Zahl sein kann, die kleiner als newMinValue (x) ist, also müssen wir eine Zahl finden, die unsere Einschränkung erfüllen kann).
Zum Zeitpunkt des Drückens von x, wenn es kleiner als prevMinvalue ist, drücken wir y [2 * x-prevMinValue] und aktualisieren newMinValue = x.
Und wenn zum Zeitpunkt des Popens der Stapel etwas weniger als den minValue enthält, ist dies unser Auslöser für die Aktualisierung des minVAlue. Wir müssen prevMinValue aus dem curMinValue und y berechnen. y = 2 * curMinValue - prevMinValue [Bewiesen] prevMinVAlue = 2 * curMinvalue - y.
2 * curMinValue - y ist die Nummer, die wir jetzt auf den prevMinValue aktualisieren müssen.
Der Code für dieselbe Logik wird unten mit der Komplexität von O (1) Zeit und O (1) Raum geteilt.
quelle
Hier ist meine Version der Implementierung.
quelle
quelle
Ich habe diese Lösung hier gefunden
quelle
quelle
quelle
quelle
Hier ist mein Code, der mit O (1) läuft. Hier habe ich ein Vektorpaar verwendet, das den Wert enthält, der gedrückt wurde, und auch den Mindestwert bis zu diesem Wert enthält.
Hier ist meine Version der C ++ - Implementierung.
quelle
quelle
Class
-MinStack
? In der Java-Dokumentation von Oracle wird empfohlen, diese zu verwendenDeque
.Eine praktische Implementierung zum Finden eines Minimums in einem Stapel von benutzerdefinierten Objekten mit dem Namen: Schule
Der Stapel speichert die Schulen im Stapel basierend auf dem Rang, der einer Schule in einer bestimmten Region zugewiesen wurde. FindMin () gibt der Schule an, wo wir die maximale Anzahl von Zulassungsanträgen erhalten, die wiederum von der Schule definiert werden Komparator, der den Rang verwendet, der den Schulen in der vorherigen Saison zugeordnet wurde.
Auch das Schulobjekt lautet wie folgt:
Dieses Beispiel behandelt Folgendes: 1. Implementierung des Stapels für benutzerdefinierte Objekte, hier Schule 2. Implementierung für die Methoden hashcode () und equals () unter Verwendung aller zu vergleichenden Objektfelder 3. Eine praktische Implementierung für das Szenario, in dem wir rqeuire, um den Stapel zu erhalten, enthält eine Operation in der Reihenfolge O (1)
quelle
language-agnostic
:): Bitte geben Sie an, was Sie für den Code verwenden (und entfernen Sie die Leerzeichen zuvorThe Code for same is below:
). Wie unterstützt diesstack.pop()
? (undpush()
?)Hier ist die PHP-Implementierung dessen, was in Jon Skeets Antwort als etwas bessere Implementierung der Raumkomplexität erklärt wurde, um das Maximum an Stack in O (1) zu erhalten.
quelle
Hier ist die C ++ - Implementierung von Jon Skeets Answer . Es ist vielleicht nicht die optimalste Art, es zu implementieren, aber es macht genau das, was es soll.
Und hier ist der Fahrer für die Klasse
Ausgabe:
quelle
Wir können dies in O (n) Zeit und O (1) Raumkomplexität tun, wie folgt:
quelle
Ich denke, Sie können einfach eine LinkedList in Ihrer Stack-Implementierung verwenden.
Wenn Sie zum ersten Mal einen Wert drücken, geben Sie diesen Wert als Kopf für die verknüpfte Liste ein.
Führen Sie dann jedes Mal, wenn Sie einen Wert drücken, wenn der neue Wert <head.data ist, eine Prepand-Operation aus (was bedeutet, dass der Kopf zum neuen Wert wird).
Wenn nicht, führen Sie eine Append-Operation durch.
Wenn Sie ein pop () machen, überprüfen Sie, ob min == linkedlist.head.data, wenn ja, dann head = head.next;
Hier ist mein Code.
quelle
quelle
quelle
Ich habe hier eine brillante Lösung gesehen: https://www.geeksforgeeks.org/design-a-stack-that-supports-getmin-in-o1-time-and-o1-extra-space/
Unten ist der Python-Code, den ich mit dem folgenden Algorithmus geschrieben habe:
quelle
Um Min-Elemente von Stack zu erhalten. Wir müssen Two Stack .ie Stack s1 und Stack s2 verwenden.
--------------------- Rufen Sie rekursiv die Schritte 2 bis 4 auf -----------------------
Wenn neues Element zum Stapel s1 hinzugefügt wurde. Dann Pop-Elemente vom Stapel s2
vergleiche neue elments mit s2. welches kleiner ist, drücke auf s2.
Pop vom Stapel s2 (der min Element enthält)
Code sieht aus wie:
quelle
Ich denke nur die Push-Operation leidet, ist genug. Meine Implementierung enthält einen Stapel von Knoten. Jeder Knoten enthält das Datenelement und auch das Minimum in diesem Moment. Dieses Minimum wird jedes Mal aktualisiert, wenn ein Push-Vorgang ausgeführt wird.
Hier sind einige Punkte zum Verständnis:
Ich habe den Stack mit Linked List implementiert.
Ein Zeiger oben zeigt immer auf das zuletzt geschobene Element. Wenn sich kein Element in diesem Stapel befindet, ist die Oberseite NULL.
Wenn ein Element verschoben wird, wird ein neuer Knoten zugewiesen, der einen nächsten Zeiger hat, der auf den vorherigen Stapel zeigt, und oben wird aktualisiert, um auf diesen neuen Knoten zu zeigen.
Der einzige Unterschied zur normalen Stack-Implementierung besteht darin, dass während des Pushs ein Mitglied min für den neuen Knoten aktualisiert wird.
Bitte schauen Sie sich den Code an, der zu Demonstrationszwecken in C ++ implementiert ist.
Und die Ausgabe des Programms sieht folgendermaßen aus:
quelle
quelle