Monotoner Stapel: nächstgrößeres Element
Beantworten Sie Bereichsanfragen in einem Durchlauf
Monotoner Stapel: nächstgrößeres Element ist eine kostenlose Coding Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 2 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des Coding Interview Prep-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Das Problem des nächsten größeren Elements
Für jede Zahl suchen Sie den ersten größeren Wert rechts von ihr. Brute Force benötigt O(n²), aber ein monotoner Stack erledigt dies in einem einzigen Durchlauf.
Was monoton bedeutet
Ein monotoner Stack hält seine Werte in sortierter Reihenfolge, hier absteigend. Sobald diese Reihenfolge verletzt würde, wissen wir, dass eine Antwort gefunden wurde.
Indizes statt Werte speichern
Legen Sie Indizes statt der reinen Zahlen auf den Stack. So wissen Sie genau, welche Position Sie ausfüllen müssen, sobald ein größeres Element auftaucht.
stack = []
ans = [-1] * len(nums)Von links nach rechts durchlaufen
Durchlaufen Sie das Array einmal. An jedem Index entfernen Sie entweder bereits aufgelöste Elemente oder legen den aktuellen Index für später auf den Stack.
for i in range(len(nums)):Die kleineren Elemente entfernen
Solange der aktuelle Wert größer ist als der Wert am obersten Index, hat dieser oberste Index endlich sein nächstes größeres Element gefunden.
while stack and nums[i] > nums[stack[-1]]:Die Antwort eintragen
Entfernen Sie den obersten Index und setzen Sie seine Antwort auf den aktuellen Wert. Jeder Index wird genau einmal aufgelöst, wodurch die Arbeit linear bleibt.
j = stack.pop()
ans[j] = nums[i]Pushen und fortfahren
Nachdem Sie alle kleineren Elemente aufgelöst haben, pushen Sie den aktuellen Index, damit er auf sein eigenes künftiges größeres Element warten kann.
stack.append(i)Übrig gebliebene Indizes haben keine Antwort
Indizes, die am Ende noch auf dem Stack liegen, haben nie einen größeren Wert gefunden. Ihr Standardwert bleibt -1, was bedeutet, dass kein solcher Wert existiert.
Warum es O(n) ist
Jeder Index wird einmal gepusht und einmal gepoppt. Auch mit der inneren while-Schleife bleibt die Gesamtarbeit über den gesamten Durchlauf linear.
Für das nächste kleinere Element umkehren
Sie benötigen stattdessen das nächste kleinere Element? Halten Sie den Stack aufsteigend, indem Sie den Vergleich von größer als auf kleiner als umstellen.
while stack and nums[i] < nums[stack[-1]]:Ein Muster, kein Trick
Bereichsabfragen, Aktienkurse und Histogrammflächen verwenden alle dieselbe Idee. Der monotone Stack ist ein wichtiges Muster für Programmierwettbewerbe, das Sie sich merken sollten.
Kurzprüfung
Sie lösen das Problem des nächsten größeren Elements mit einem monotonen Stack. Warum ist die Gesamtlaufzeit linear?
Zusammenfassung: Ein Durchlauf, viele Antworten
Sie haben einen absteigenden monotonen Stack aus Indizes verwendet, um nächste größere Elemente in O(n) zu finden. Dieses Muster eröffnet viele Probleme mit Bereichsabfragen. 🚀
Häufig gestellte Fragen
Ist die Lektion „Monotoner Stapel: nächstgrößeres Element“ kostenlos?
Ja — der vollständige Text von „Monotoner Stapel: nächstgrößeres Element“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des Coding Interview Prep-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der Coding Interview Prep-Kurs umfasst insgesamt 4 Lektionen.
Was lerne ich in „Monotoner Stapel: nächstgrößeres Element“?
Beantworten Sie Bereichsanfragen in einem Durchlauf Du übst Coding Interview Prep mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.
Brauche ich Erfahrung, um Coding Interview Prep zu starten?
Keine Vorkenntnisse erforderlich. Coding Interview Prep auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 2 von 4.
Wie lange dauert die Lektion „Monotoner Stapel: nächstgrößeres Element“?
Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.
Kann ich in dieser Coding Interview Prep-Lektion Code schreiben und ausführen?
Ja. Jede Coding Interview Prep-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.
Alle Lektionen in diesem Kurs
- Stapel zum Abgleichen von Klammern
- Monotoner Stapel: nächstgrößeres Element
- Warteschlangen und collections.deque
- Maximum im Sliding Window mit Deque