Next Greater Element I
Du erhältst zwei Arrays aus unterschiedlichen Ganzzahlen, nums1 und nums2, und jeder Wert von nums1 kommt auch in nums2 vor. Das nächstgrößere Element eines Werts x ist der erste Wert rechts von x in nums2, der größer als x ist, oder -1, wenn kein solcher Wert existiert.
Gib ein Array zurück, das das nächstgrößere Element jedes Werts von nums1 in der Reihenfolge von nums1 enthält.
Funktion
- nums1integer-array
- die zu beantwortenden Werte, die sich alle in nums2 befinden
- nums2integer-array
- das Array, in dem du rechts von jedem Wert nachsiehst
- Gibt zurückinteger-array
- das nächstgrößere Element jedes Werts von nums1 oder -1, in der Reihenfolge von nums1
Einschränkungen
1 ≤ nums1.length ≤ nums2.length ≤ 1040 ≤ nums1[i], nums2[i] ≤ 104- Alle Werte in
nums1sind verschieden, und alle Werte innums2sind verschieden. - Jeder Wert von
nums1kommt innums2vor.
Beispiele
- Eingabe
- nums1 = [3, 8, 1]nums2 = [1, 6, 3, 8, 2]
- Ausgabe
- [8, -1, 6]
- Erklärung
- Auf die 3 in
nums2folgen 8 und 2, und 8 ist die erste Zahl, die größer als 3 ist. Auf die 8 folgt nur 2, daher erhält 8 den Wert -1. Der Wert direkt nach 1 ist 6, der bereits größer ist.
- Eingabe
- nums1 = [5, 2]nums2 = [2, 9, 5, 4]
- Ausgabe
- [-1, 9]
- Erklärung
- Nur auf die 5 folgt die 4, und 4 ist kleiner, also erhält 5 den Wert -1. Der Wert direkt nach 2 ist 9. Die Antworten folgen der Reihenfolge von
nums1, nicht der Reihenfolge vonnums2.
- Eingabe
- nums1 = [10, 0]nums2 = [0, 10, 11]
- Ausgabe
- [11, 10]
- Erklärung
- Der erste Wert nach 10 ist 11. Der erste Wert nach 0 ist 10, was größer ist, also erhält 0 den Wert 10, obwohl 11 später kommt und noch größer ist.
+14 versteckte Tests beim Einreichen
Weiterführende Frage
Kannst du für jede Position von nums2 mit demselben einzigen Durchlauf zurückgeben, wie viele Schritte rechts davon das nächste größere Element liegt?
Tipps
Öffne sie nacheinander. Jeder verrät ein bisschen mehr.
Das Durchsuchen der Werte rechts von jedem Wert in
nums1kann bis zu 10^4 Schritte pro Wert kosten. Die Antworten hängen nur vonnums2ab. Kannst du in einem Durchlauf das nächstgrößere Element für jeden Wert innums2ermitteln und anschließend die Werte vonnums1nachschlagen?Gehe
nums2von links nach rechts durch und behalte die Werte, denen noch kein größerer Wert begegnet ist. Wenn ein neuer Wert hinzukommt, ist er die Antwort für jeden wartenden Wert, der kleiner ist als er. Die wartenden Werte bilden immer eine absteigende Folge, sodass die kleineren oben auf einem Stapel liegen.Für jeden Wert von
nums2: Solange der oberste Wert des Stacks kleiner ist als dieser Wert, entferne ihn vom Stack und speichere den aktuellen Wert als seine Antwort in einer Hash-Map. Füge dann den aktuellen Wert hinzu. Gib am Ende für jeden Wert vonnums1die Antwort aus der Map zurück, bei einem Wert, der nie entfernt wurde, -1.
Lösung
Für einen einzelnen Wert besteht die Antwort aus einer Suche rechts davon, aber eine Suche für jeden Wert von nums1 kostet bis zu nums1.length × nums2.length Schritte. Die Antworten hängen nur von nums2 ab, daher kannst du mit einem monotonen Stack auf einmal das nächstgrößere Element für jeden Wert von nums2 finden, sie in einer Hash-Map speichern und die Werte für nums1 durch Nachschlagen ermitteln.
Finde jeden Wert und durchsuche nach rechts
Korrekt, wird aber bei den größten Tests nicht fertig
Idee
Tu, was die Definition vorgibt. Gehe für einen Wert x aus nums1 durch nums2, bis du x erreichst. Gehe dann weiter und halte beim ersten größeren Wert an. Wenn du das Ende erreichst, ohne einen zu finden, lautet die Antwort -1.
Das ist korrekt, weil der Scan die Werte rechts von x der Reihe nach besucht. Der erste größere Wert, auf den er trifft, ist also der erste größere Wert überhaupt.
Das ist langsam, wenn die Antworten weit entfernt sind oder fehlen. Wenn nums2 absteigend sortiert ist, findet kein Scan jemals einen größeren Wert, und jeder Wert aus nums1 wird bis zum Ende durchlaufen. Bei m Werten in nums1 und n in nums2 sind das bis zu m × n Schritte: 10^8, wenn beide Arrays 10^4 Werte enthalten. Jeder Scan durchläuft außerdem erneut Bereiche, die frühere Scans bereits durchlaufen haben.
Algorithmus
- Durchlaufe jeden Wert
xinnums1. - Finde den Index
j, an demnums2[j]gleichxist. - Durchsuche
nums2abj+1und halte beim ersten Wert an, der größer alsxist. - Füge diesen Wert hinzu oder -1, falls die Suche das Ende erreicht hat.
- Gib die gesammelten Antworten zurück.
def nextGreaterElement(nums1, nums2):
result = []
for x in nums1:
j = 0
while nums2[j] != x:
j += 1
answer = -1
for k in range(j + 1, len(nums2)):
if nums2[k] > x:
answer = nums2[k]
break
result.append(answer)
return resultMonotoner Stack und eine Hash-Map
Idee
Dreh die Frage um. Statt für jeden Wert zu fragen, was nach ihm kommt, durchläufst du nums2 einmal und lässt jeden neuen Wert die früheren Werte beantworten, die er übertrifft. Die Werte, auf die noch keine Antwort vorliegt, legst du auf einen Stack. Sobald ein Wert eintrifft, entfernst du alle kleineren Werte von der Spitze: Der neue Wert ist der erste größere Wert rechts von ihnen und damit ihre Antwort. Dann legst du den neuen Wert auf den Stack, denn für ihn steht die Antwort noch aus.
Gehen wir nums2 = [1, 6, 3, 8, 2] durch. Lege 1 auf den Stack. Dann kommt 6 und übertrifft 1, also ordnest du 1 den Wert 6 zu; lege 6 auf den Stack. Dann kommt 3, übertrifft 6 nicht und wird oben auf den Stack gelegt: Der Stack ist [6, 3]. Dann entfernt 8 die Werte 3 und 6, also ordnest du beiden den Wert 8 zu; lege 8 auf den Stack. Dann wird 2 auf den Stack gelegt. Am Ende enthält der Stack [8, 2], und für diese beiden gibt es keine Antwort. Für nums1 = [3, 8, 1] liefert die Zuordnung [8, -1, 6].
Der Stack ist von unten nach oben immer absteigend sortiert, denn ein Wert wird erst dann auf den Stack gelegt, wenn alle kleineren Werte über ihm entfernt wurden. Deshalb musst du immer nur die Spitze betrachten. Ein Wert verlässt den Stack, sobald der erste größere Wert auftaucht. Daher hältst du als Antwort den ersten fest, nicht den größten.
Jeder Wert von nums2 wird einmal auf den Stack gelegt und höchstens einmal entfernt. Daher führt die innere Schleife über den gesamten Durchlauf hinweg insgesamt höchstens n Entfernungen aus. Zusammen mit den m Nachschlagevorgängen beträgt die Laufzeit O(n + m). Die Map verknüpft die beiden Arrays: Die Werte sind eindeutig, deshalb eignet sich ein Wert als Schlüssel, auch wenn er in nums1 und nums2 an unterschiedlichen Positionen steht. Die C- und R-Lösungen verwenden als Map ein Array mit 10^4+1 Einträgen, dessen Indizes den Werten entsprechen. Das funktioniert, weil kein Wert 10^4 überschreitet.
Algorithmus
- Erstelle eine leere Map und einen leeren Stack.
- Entferne für jeden Wert von
nums2alle kleineren Werte von der Spitze des Stacks und ordne sie dem aktuellen Wert zu. - Lege den aktuellen Wert auf den Stack.
- Gib für jeden Wert von
nums1die zugeordnete Antwort zurück oder -1, falls es keine gibt.
def nextGreaterElement(nums1, nums2):
next_greater = {}
stack = [] # values still waiting for a greater one, decreasing from bottom to top
for value in nums2:
# value is the first greater value to the right of every smaller value on the stack.
while stack and stack[-1] < value:
next_greater[stack.pop()] = value
stack.append(value)
# Whatever is still on the stack has no greater value to its right.
return [next_greater.get(x, -1) for x in nums1]
Stolperfallen und Grenzfälle
Der Stack selbst ist kurzer Code; die Fehler liegen darin, was du speicherst und wo du nachsiehst.
- Den größten Wert rechts statt des ersten größeren Werts speichern. In
nums2 = [3, 5, 1, 2, 4, 9, 0]ist die Antwort für 1 die 2, nicht die 9. - Die Antworten in der Reihenfolge von
nums2oder für jeden Wert vonnums2zurückgeben. Das Ergebnis hat einen Eintrag pro Wert vonnums1, und zwar in dessen Reihenfolge. - Einen Index statt eines Werts zurückgeben. Das Problem fragt nach dem größeren Wert selbst.
nums2an dem Index lesen, den ein Wert innums1hat. Derselbe Wert steht in den beiden Arrays an unterschiedlichen Positionen; finde ihn über seinen Wert, dafür ist die Map da.- Die Werte vergessen, die am Ende noch auf dem Stack liegen. Sie sind keinem größeren Wert begegnet, daher lautet ihre Antwort -1; eine Map-Abfrage ohne Standardwert schlägt fehl oder liefert für sie nichts zurück.
- Nach links schauen oder zum Anfang von
nums2übergehen. Es zählen nur Werte rechts davon, und das Array wird nicht zyklisch durchlaufen.
Häufige Fragen4
Wie hoch ist die Zeitkomplexität von Next Greater Element I?
Die Lösung mit dem monotonen Stapel benötigt O(n + m) Zeit, wobei n die Länge von nums2 und m die Länge von nums1 ist. Jeder Wert von nums2 wird höchstens einmal auf den Stapel gelegt und wieder entfernt, und für jeden Wert von nums1 erfolgt eine Suche in der Map. Die Map und der Stapel benötigen O(n) Speicherplatz. Das Scannen nach rechts von jedem Wert aus benötigt O(n·m) Zeit.
Was ist ein monotoner Stack?
Es ist ein Stapel, dessen Werte von unten nach oben sortiert bleiben, hier absteigend. Bevor du einen neuen Wert hinzufügst, entfernst du alle Werte, die die Reihenfolge verletzen würden, und bei diesen Entfernungen geschieht die eigentliche Arbeit: Jeder entfernte Wert hat seinen ersten größeren Wert rechts von sich gefunden. Damit lassen sich Aufgaben zu den nächsten größeren, den nächsten kleineren und ähnlichen Werten in linearer Zeit lösen.
Warum benötigt Next Greater Element I eine Hash-Map?
Der Stack-Durchlauf liefert die Antworten in der Reihenfolge, in der die Werte den Stack verlassen, und ordnet sie den Werten von nums2 zu. Die Ausgabe muss der Reihenfolge von nums1 folgen, in der sich dieselben Werte an anderen Positionen befinden. Da alle Werte eindeutig sind, verbindet eine Abbildung von Werten auf Antworten die beiden Arrays mit einer Suche konstanter Zeit pro Wert.
Was ändert sich, wenn nums2 zirkulär ist?
Dann kann die Suche nach einem größeren Wert am Anfang des Arrays fortgesetzt werden. Führe denselben Stack-Durchlauf zweimal über das Array aus, wobei du den Index i % n für i von 0 bis 2n-1 verwendest, und füge Werte nur während des ersten Durchlaufs hinzu. Werte, die nach beiden Durchläufen noch auf dem Stack liegen, haben nirgends einen größeren Wert, daher ist ihre Antwort -1.
Ähnliche Aufgaben
Aufgaben mit denselben Ideen. Wer zwei oder drei davon löst, behält das Muster.
Python
def nextGreaterElement(nums1, nums2):
# Schreibe hier den CodeFall 1
Fall 2
Fall 3
Eingabe
nums1 = [3, 8, 1] nums2 = [1, 6, 3, 8, 2]
Erwartet
[8, -1, 6]