Monotoner Stack: aufsteigend vs. absteigend
Verwalten Sie einen auf- oder absteigenden Stack, um Abfragen nach dem nächsten größeren und dem vorherigen kleineren Element effizient in O(n) zu beantworten.
Monotoner Stack: aufsteigend vs. absteigend ist eine kostenlose Coding Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 1 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.
Was ist ein monotoner Stack?
Ein monotoner Stack ist ein Stack, der die Elemente in einer sortierten Reihenfolge hält (entweder vom unteren zum oberen Ende immer aufsteigend oder immer absteigend). Bevor Sie ein neues Element auf den Stack legen, entfernen Sie alle Elemente, die die monotone Invariante verletzen. Diese eingeschränkte Struktur ermöglicht O(n)-Lösungen für Probleme, die andernfalls verschachtelte Schleifen mit O(n²) erfordern würden.
Die entscheidende Erkenntnis: Jedes Element wird höchstens einmal auf den Stack gelegt und höchstens einmal entfernt. Daher beträgt die Gesamtzahl der Operationen beim Durchlaufen des gesamten Arrays O(n) — nicht O(n²). In dem Moment, in dem wir ein Element entfernen, haben wir die Antwort gefunden, auf die es gewartet hat.
# Monotonic increasing stack (bottom to top: smallest to largest)
stack = []
for val in [3, 1, 4, 1, 5, 9, 2, 6]:
while stack and stack[-1] > val:
stack.pop() # maintain increasing invariant
stack.append(val)
print('Increasing stack (left-to-right):', stack) # [1, 1, 2, 6]
# Monotonic decreasing stack (bottom to top: largest to smallest)
stack = []
for val in [3, 1, 4, 1, 5, 9, 2, 6]:
while stack and stack[-1] < val:
stack.pop() # maintain decreasing invariant
stack.append(val)
print('Decreasing stack (left-to-right):', stack) # [9, 6]Nächstgrößeres Element I
Beim Problem Next Greater Element soll für jedes Element das erste größere Element rechts davon gefunden werden. Eine Brute-Force-Doppelschleife mit O(n²) ist zu langsam. Mit einem monoton absteigenden Stack lösen wir das Problem in O(n).
Verarbeiten Sie die Elemente von links nach rechts. Bevor Sie Element i auf den Stack legen, entfernen Sie alle Elemente aus dem Stack, die kleiner als nums[i] sind — nums[i] ist für jedes dieser Elemente das nächstgrößere Element. Nach der Verarbeitung aller Elemente haben alle noch im Stack befindlichen Elemente kein größeres Element rechts von sich (Ergebnis = -1).
def next_greater_element(nums):
n = len(nums)
result = [-1] * n
stack = [] # stores indices; stack values are decreasing
for i in range(n):
# Pop elements smaller than nums[i]
while stack and nums[stack[-1]] < nums[i]:
idx = stack.pop()
result[idx] = nums[i] # nums[i] is next greater for idx
stack.append(i)
# Remaining elements in stack have no next greater => keep -1
return result
nums = [2, 1, 2, 4, 3]
print(next_greater_element(nums)) # [4, 2, 4, -1, -1]
nums2 = [1, 3, 2, 4]
print(next_greater_element(nums2)) # [3, 4, 4, -1]Nächstgrößeres Element: Ablauf des Algorithmus
Sehen wir uns [2, 1, 2, 4, 3] Schritt für Schritt an. Wir verwalten einen absteigenden Stack mit Indizes, für deren nächstgrößeres Element wir noch keines gefunden haben.
- i=0, val=2: Stack ist leer, 0 wird hinzugefügt. Stack: [0]
- i=1, val=1: 1 < nums[0]=2, 1 wird hinzugefügt. Stack: [0,1]
- i=2, val=2: 1 wird entfernt (nums[1]=1 < 2), result[1]=2; nun gilt nums[0]=2 nicht < 2, daher wird 2 hinzugefügt. Stack: [0,2]
- i=3, val=4: 2 wird entfernt (result[2]=4), 0 wird entfernt (result[0]=4), 3 wird hinzugefügt. Stack: [3]
- i=4, val=3: 3 < nums[3]=4, 4 wird hinzugefügt. Stack: [3,4]
- Ende: Für die Elemente im Stack [3,4] gilt result=-1
def next_greater_trace(nums):
n = len(nums)
result = [-1] * n
stack = []
for i in range(n):
print(f'i={i} val={nums[i]}: stack={[nums[s] for s in stack]}', end=' => ')
while stack and nums[stack[-1]] < nums[i]:
idx = stack.pop()
result[idx] = nums[i]
print(f'pop {nums[idx]}, NGE={nums[i]};', end=' ')
stack.append(i)
print(f'push {nums[i]}, stack={[nums[s] for s in stack]}')
print('Result:', result)
return result
next_greater_trace([2, 1, 2, 4, 3])Vorheriges kleineres Element
Monotone Stacks können auch Abfragen nach dem vorherigen kleineren Element (PSE) beantworten: Für jedes Element wird das nächstgelegene kleinere Element links davon gesucht. Anstatt bei einem größeren Element Elemente zu entfernen, entfernen wir Elemente bei einem größeren oder gleich großen Element und speichern die oberste Position des Stacks als PSE, bevor wir das aktuelle Element hinzufügen.
Die Richtung ändert sich: Wir verarbeiten die Elemente weiterhin von links nach rechts, beantworten die Fragen aber nicht beim Entfernen, sondern unmittelbar vor dem Hinzufügen. Das oberste Element des Stacks ist in diesem Moment das nächstgelegene kleinere Element links. Ist der Stack leer, gibt es links kein kleineres Element (Ergebnis = -1 oder ein Sentinel-Wert).
def previous_smaller_element(nums):
n = len(nums)
result = [-1] * n
stack = [] # monotonic increasing (values increase bottom to top)
for i in range(n):
# Pop elements >= current (maintain strictly increasing invariant)
while stack and nums[stack[-1]] >= nums[i]:
stack.pop()
# Top of stack is previous smaller element (if exists)
if stack:
result[i] = nums[stack[-1]]
stack.append(i)
return result
nums = [4, 5, 2, 10, 8]
print('PSE:', previous_smaller_element(nums)) # [-1, 4, -1, 2, 2]
nums2 = [1, 3, 2, 5, 4]
print('PSE:', previous_smaller_element(nums2)) # [-1, 1, 1, 2, 2]Tägliche Temperaturen: Auf wärmere Tage warten
Beim Problem Daily Temperatures (LeetCode 739) erhalten Sie tägliche Temperaturen und sollen ein Array zurückgeben, dessen Elemente jeweils die Anzahl der Tage bis zu einer wärmeren Temperatur enthalten. Dies entspricht genau dem Muster des nächstgrößeren Elements. Statt des größeren Werts benötigen wir jedoch die Anzahl der Tage (die Differenz der Indizes).
Verwenden Sie einen monoton absteigenden Stack mit Indizes. Wenn wir am Index i eine wärmere Temperatur finden, entfernen wir alle Indizes j aus dem Stack, für die temps[j] < temps[i] gilt, und setzen result[j] = i - j. Für die verbleibenden Indizes gibt es keinen späteren wärmeren Tag (result = 0).
def daily_temperatures(temperatures):
n = len(temperatures)
result = [0] * n
stack = [] # indices of unresolved days
for i in range(n):
while stack and temperatures[stack[-1]] < temperatures[i]:
j = stack.pop()
result[j] = i - j # days until warmer
stack.append(i)
return result
temps = [73, 74, 75, 71, 69, 72, 76, 73]
print(daily_temperatures(temps)) # [1, 1, 4, 2, 1, 1, 0, 0]
temps2 = [30, 40, 50, 60]
print(daily_temperatures(temps2)) # [1, 1, 1, 0] (always warmer next day)
temps3 = [30, 60, 90]
print(daily_temperatures(temps3)) # [1, 1, 0]Aufsteigender vs. absteigender Stack: Wann Sie welchen verwenden
Die richtige Richtung des Stacks zu wählen, ist entscheidend:
- Monoton absteigender Stack (Entfernen, wenn current > top): beantwortet Abfragen nach dem nächstgrößeren Element und dem vorherigen größeren Element. Wird bei daily-temperatures, largest-rectangle und trap-rain-water verwendet.
- Monoton aufsteigender Stack (Entfernen, wenn current < top): beantwortet Abfragen nach dem nächstkleineren Element und dem vorherigen kleineren Element. Wird beim Ermitteln der Spanne von Aktienkursen und der Anzahl sichtbarer Personen in einer Warteschlange verwendet.
Denken Sie daran: Das Element, das ein Entfernen auslöst, ist die Antwort auf die Abfrage des entfernten Elements – entweder das nächstgrößere oder das nächstkleinere Element, abhängig davon, welche Invariante Sie aufrechterhalten.
# Summary: which stack type for which query?
queries = {
'Next Greater Element': 'Decreasing stack (pop when new > top)',
'Next Smaller Element': 'Increasing stack (pop when new < top)',
'Previous Greater Element': 'Decreasing stack (answer = top before push)',
'Previous Smaller Element': 'Increasing stack (answer = top before push)',
}
for query, approach in queries.items():
print(f'{query}:\n => {approach}\n')
# Mnemonic:
# NGE/PGE => decreasing stack (we pop smaller elements, finding their next/prev larger)
# NSE/PSE => increasing stack (we pop larger elements, finding their next/prev smaller)Zirkuläres nächstgrößeres Element
Next Greater Element II (LeetCode 503): Bei einem zirkulären Array, dessen Ende wieder an den Anfang anschließt, soll das nächstgrößere Element gefunden werden. Der Trick besteht darin, das Array zweimal zu verarbeiten, indem die Indizes verdoppelt werden: Durchlaufen Sie die Indizes von 0 bis 2n-1 und verwenden Sie index % n, um zum Anfang zurückzuspringen. Fügen Sie nur Indizes von 0 bis n-1 hinzu (im ersten Durchlauf), damit Elemente nicht doppelt gezählt werden.
Alternativ können Sie das Array im zweiten Durchlauf verarbeiten, ohne neue Indizes hinzuzufügen – Sie entfernen dann nur Elemente. So wird der zirkuläre Blick nach vorn korrekt behandelt, ohne das Array tatsächlich zu duplizieren; der benötigte Speicher bleibt O(n).
def next_greater_element_circular(nums):
n = len(nums)
result = [-1] * n
stack = []
for i in range(2 * n):
while stack and nums[stack[-1]] < nums[i % n]:
idx = stack.pop()
result[idx] = nums[i % n]
if i < n:
stack.append(i) # only push real indices (0..n-1)
return result
print(next_greater_element_circular([1, 2, 1])) # [2, -1, 2]
print(next_greater_element_circular([1, 2, 3, 4, 3])) # [2, 3, 4, -1, 4]
print(next_greater_element_circular([5, 4, 3, 2, 1])) # [-1, 5, 5, 5, 5]Aktienkurs-Spannenproblem
Beim Problem Stock Span erhalten Sie tägliche Aktienkurse und sollen für jeden Tag die Spanne berechnen – die Anzahl aufeinanderfolgender vorheriger Tage, deren Kurs kleiner oder gleich dem heutigen Kurs ist. Dies ist im Grunde das Problem des vorherigen größeren Elements: Die Spanne ist der Abstand vom heutigen Tag zum nächstgelegenen Tag mit einem strikt höheren Kurs.
Verwenden Sie einen monoton absteigenden Stack. Entfernen Sie bei der Verarbeitung von Tag i alle Tage mit einem Kurs ≤ dem aktuellen Kurs. Die Spanne ist i - stack[-1], wenn der Stack nicht leer ist, oder i + 1, wenn er leer ist (der Kurs ist bisher das Maximum). Fügen Sie anschließend i hinzu.
def stock_span(prices):
spans = []
stack = [] # indices of prices forming decreasing sequence
for i, price in enumerate(prices):
while stack and prices[stack[-1]] <= price:
stack.pop()
span = i - stack[-1] if stack else i + 1
spans.append(span)
stack.append(i)
return spans
prices = [100, 80, 60, 70, 60, 75, 85]
print('Prices:', prices)
print('Spans: ', stock_span(prices)) # [1, 1, 1, 2, 1, 4, 6]
# Verification for day 5 (price=75): prev higher is day 1 (80), span = 5-1 = 4
# Day 6 (price=85): prev higher is day 0 (100), span = 6-0 = 6Monotoner Stack für sichtbare Personen in einer Warteschlange
Beim Problem Number of Visible People in a Queue stehen Personen mit jeweils einer bestimmten Körpergröße in einer Warteschlange. Person i kann Person j (j > i) sehen, wenn alle Personen dazwischen kleiner sind als beide. Dafür wird ein monoton absteigender Stack verwendet.
Verarbeiten Sie die Personen von rechts nach links. Verwalten Sie einen absteigenden Stack mit Körpergrößen. Zählen Sie für jede Person, wie viele Personen sie sehen kann: Entfernen Sie alle kleineren Personen (sie sind sichtbar, werden danach aber verdeckt) und addieren Sie 1, wenn der Stack anschließend nicht leer ist (die erste größere Person ist ebenfalls sichtbar). Insgesamt ergibt sich O(n), da jede Person höchstens einmal hinzugefügt und einmal entfernt wird.
def visible_people(heights):
n = len(heights)
result = [0] * n
stack = [] # decreasing monotonic stack (heights)
for i in range(n - 1, -1, -1): # right to left
count = 0
while stack and stack[-1] < heights[i]:
stack.pop()
count += 1 # can see this shorter person
if stack:
count += 1 # can see the first person >= heights[i]
result[i] = count
stack.append(heights[i])
return result
heights = [10, 6, 8, 5, 11, 9]
print('Heights:', heights)
print('Visible:', visible_people(heights)) # [3, 1, 2, 1, 1, 0]Garantie für O(n): Warum jedes Element höchstens einmal hinzugefügt und entfernt wird
Die Laufzeitgarantie O(n) monotoner Stack-Algorithmen ergibt sich aus einem einfachen amortisierten Argument: Jedes Element wird genau einmal auf den Stack gelegt und höchstens einmal entfernt. Kein Element kann mehr als einmal hinzugefügt oder entfernt werden. Daher gibt es über die gesamte Schleife hinweg höchstens 2n Operationen zum Hinzufügen und Entfernen. Die Gesamtarbeit beträgt also O(n), obwohl die verschachtelte while-Schleife zunächst O(n²) nahezulegen scheint.
Diese amortisierte Analyse sollten Sie in Vorstellungsgesprächen erläutern können. Die while-Schleife wird nicht in jeder Iteration n-mal ausgeführt – sie entfernt nur so viele Elemente, wie zuvor im Stack gewartet haben. Nach dem Entfernen sind diese Elemente endgültig verschwunden.
def next_greater_instrumented(nums):
result = [-1] * len(nums)
stack = []
pushes = pops = 0
for i in range(len(nums)):
while stack and nums[stack[-1]] < nums[i]:
idx = stack.pop()
result[idx] = nums[i]
pops += 1
stack.append(i)
pushes += 1
print(f'n={len(nums)}, pushes={pushes}, pops={pops}')
print(f'Total operations = {pushes + pops} <= 2n = {2*len(nums)}')
return result
import random
nums = random.sample(range(1000), 100)
next_greater_instrumented(nums)
# Confirm: total operations always <= 2nMonotone-Stack-Probleme erkennen
Ein Problem benötigt wahrscheinlich einen monotonen Stack, wenn es nach dem nächstgelegenen größeren oder kleineren Element, der Spanne von Preisen, sichtbaren Elementen in einer Reihe oder Flächen auf Grundlage eines Histogramms fragt. Achten Sie auf diese Schlüsselwörter und Muster: Für jedes Element wird die Antwort vom nächstgelegenen relevanten Element in eine Richtung (links oder rechts) benötigt.
Wenn eine Brute-Force-Lösung für jedes Element nach links oder rechts scannt (O(n²)), ersetzen Sie diesen Scan durch einen monotonen Stack. Der Stack „merkt“ sich mögliche Antworten, verwirft irrelevante Elemente und entfernt die richtige Antwort genau in dem Moment, in dem sie benötigt wird.
# Monotonic stack problem recognition guide
patterns = [
('Next/previous greater element', 'Decreasing stack; answer found on pop'),
('Next/previous smaller element', 'Increasing stack; answer found on pop'),
('Days until warmer/colder', 'Stack of indices; answer = i - j'),
('Stock span', 'Decreasing stack; span = i - prev larger idx'),
('Largest rectangle in histogram', 'Increasing stack; area computed on pop'),
('Trapping rain water', 'Decreasing stack or two-pointer'),
('Sliding window maximum', 'Decreasing deque of indices'),
]
print('Monotonic Stack / Deque Pattern Guide:')
print('='*60)
for problem, approach in patterns:
print(f'Problem: {problem}')
print(f' Approach: {approach}')
print()Kurze Überprüfung
Testen Sie Ihr Verständnis der Konzepte aus dieser Lektion zu Data Structures & Algorithms — Coding Interview Prep.
Zusammenfassung der Lektion
In dieser Lektion haben Sie gelernt: Ein monotoner Stack erhält eine aufsteigende oder absteigende Reihenfolge, indem er vor dem Hinzufügen Elemente entfernt, die die Invariante verletzen, ein absteigender Stack beantwortet Fragen nach dem nächsten oder vorherigen größeren Element, während ein aufsteigender Stack Fragen nach dem nächsten oder vorherigen kleineren Element beantwortet, und jedes Element höchstens einmal hinzugefügt und entfernt wird, wodurch sich insgesamt O(n) statt O(n²) ergibt. Als Nächstes wenden wir den monotonen Stack an, um das größte Rechteck in einem Histogramm zu finden.
Häufig gestellte Fragen
Ist die Lektion „Monotoner Stack: aufsteigend vs. absteigend“ kostenlos?
Ja — der vollständige Text von „Monotoner Stack: aufsteigend vs. absteigend“ 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 Stack: aufsteigend vs. absteigend“?
Verwalten Sie einen auf- oder absteigenden Stack, um Abfragen nach dem nächsten größeren und dem vorherigen kleineren Element effizient in O(n) zu beantworten. 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 1 von 4.
Wie lange dauert die Lektion „Monotoner Stack: aufsteigend vs. absteigend“?
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
- Monotoner Stack: aufsteigend vs. absteigend
- Größtes Rechteck im Histogramm
- Sliding-Window-Maximum mit monotoner Deque
- Trapping Rain Water: Stack und Zwei-Zeiger