Muster des monotonen Stapels
Wenden Sie den monotonen Stapel an, um daily-temperatures, largest-rectangle-in-histogram und next-greater-element in O(n) zu lösen.
Muster des monotonen Stapels ist eine kostenlose Coding Interview Prep-Lektion auf CoddyKit. Dies ist Lektion 3 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 über seine Elemente hinweg eine sortierte Invariante aufrechterhält. Ein monoton steigender Stack enthält von unten nach oben steigende Elemente; ein monoton fallender Stack enthält von unten nach oben fallende Elemente. Wenn ein neues Element die Invariante verletzt, werden Elemente entfernt, bis die Invariante wiederhergestellt ist; anschließend wird das neue Element auf den Stack gelegt.
Dieser einfache Mechanismus ermöglicht Antworten in O(n) auf Abfragen nach dem „nächstgrößeren Element“ und dem „nächstkleineren Element“, für die naive verschachtelte Schleifen in O(n²) erforderlich wären.
# Build a monotonically increasing stack from [3,1,2,5,4]
nums = [3, 1, 2, 5, 4]
stack = []
for n in nums:
while stack and stack[-1] > n:
stack.pop() # remove elements that violate increasing order
stack.append(n)
print('stack:', stack)Nächstgrößeres Element (LeetCode 496)
Finden Sie für jedes Element das erste Element rechts davon, das strikt größer ist. Eine Brute-Force-Lösung in O(n²) durchsucht von jeder Position aus die Elemente rechts davon. Der Ansatz mit monotonem Stack: Verwalten Sie einen fallenden Stack aus Indizes. Wenn ein größeres Element gefunden wird, entfernen Sie alle Indizes kleinerer Elemente – deren „nächstgrößeres Element“ ist das aktuelle Element. Für die verbleibenden Indizes gibt es kein nächstgrößeres Element (Ergebnis ist -1).
def nextGreaterElement(nums):
n = len(nums)
result = [-1] * n
stack = [] # indices, decreasing values
for i, val in enumerate(nums):
while stack and nums[stack[-1]] < val:
j = stack.pop()
result[j] = val
stack.append(i)
return result
print(nextGreaterElement([2, 1, 2, 4, 3])) # [4, 2, 4, -1, -1]
print(nextGreaterElement([1, 3, 2, 4])) # [3, 4, 4, -1]Nächstgrößeres Element in einem zirkulären Array
LeetCode 503 „Next Greater Element II“: dasselbe Problem, aber das Array wird als zirkulär betrachtet. Nach dem Ende wird zum Anfang zurückgesprungen und dort weitergeprüft. Der Trick: Durchlaufen Sie das Array zweimal (Indizes 0 bis 2n-1) und verwenden Sie i % n, um auf das ursprüngliche Array zuzugreifen. Legen Sie nur Indizes im Bereich [0, n-1] auf den Stack, um doppelte Verarbeitung zu vermeiden.
def nextGreaterElements(nums):
n = len(nums)
result = [-1] * n
stack = []
for i in range(2 * n):
while stack and nums[stack[-1]] < nums[i % n]:
j = stack.pop()
result[j] = nums[i % n]
if i < n:
stack.append(i)
return result
print(nextGreaterElements([1, 2, 1])) # [2, -1, 2]
print(nextGreaterElements([5, 4, 3, 2, 1])) # [-1, 5, 5, 5, 5]Tägliche Temperaturen: Vollständige Lösung
LeetCode 739 erneut: Wie viele Tage dauert es für jeden Tag bis zu einer wärmeren Temperatur? Der monotone Stack enthält Indizes von Tagen mit Temperaturen in absteigender Reihenfolge. Wenn ein wärmerer Tag i gefunden wird, entfernen Sie alle Indizes j kälterer Tage vom Stack und speichern Sie result[j] = i - j. Tage, die im Stack verbleiben, finden nie einen wärmeren Tag; ihr Ergebnis bleibt daher 0.
def dailyTemperatures(temperatures):
n = len(temperatures)
result = [0] * n
stack = [] # indices, decreasing temperatures
for i, t in enumerate(temperatures):
while stack and temperatures[stack[-1]] < t:
j = stack.pop()
result[j] = i - j
stack.append(i)
return result
temps = [73, 74, 75, 71, 69, 72, 76, 73]
print(dailyTemperatures(temps))
# [1, 1, 4, 2, 1, 1, 0, 0]Vorheriges kleineres Element
Die Abfrage nach dem „vorherigen kleineren Element“ fragt: Was ist für jedes Element der nächste kleinere Wert links davon? Verwenden Sie einen monoton steigenden Stack und verarbeiten Sie die Elemente von links nach rechts. Bevor Sie den Index i auf den Stack legen, ist das oberste Stack-Element das vorherige kleinere Element (denn alle Elemente, die größer als nums[i] sind, wurden bei vorherigen Einfügungen bereits entfernt, als größere Elemente sie vom Stack entfernten).
def previousSmallerElement(nums):
n = len(nums)
result = [-1] * n
stack = [] # indices, increasing values
for i, val in enumerate(nums):
while stack and nums[stack[-1]] >= val:
stack.pop()
if stack:
result[i] = nums[stack[-1]]
stack.append(i)
return result
print(previousSmallerElement([4, 5, 2, 10, 8])) # [-1, 4, -1, 2, 2]
print(previousSmallerElement([3, 1, 2])) # [-1, -1, 1]Größtes Rechteck im Histogramm
LeetCode 84 „Largest Rectangle in Histogram“: ein monoton steigender Stack aus Indizes. Für jeden Balken entfernen Sie alle Balken, die höher als der aktuelle sind. Für jeden entfernten Balken h ist seine rechte Grenze der aktuelle Index i und seine linke Grenze das neue oberste Stack-Element + 1 (oder 0, wenn der Stack leer ist). Fläche = h × (right - left). Fügen Sie am Ende einen Wächter mit Höhe 0 hinzu, um das Entfernen aller verbleibenden Balken zu erzwingen.
def largestRectangleArea(heights):
heights = heights + [0] # sentinel
stack = [] # indices, increasing heights
result = 0
for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()]
left = stack[-1] + 1 if stack else 0
width = i - left
result = max(result, height * width)
stack.append(i)
return result
print(largestRectangleArea([2, 1, 5, 6, 2, 3])) # 10
print(largestRectangleArea([2, 4])) # 4
print(largestRectangleArea([1])) # 1Maximales Rechteck (LeetCode 85)
LeetCode 85 „Maximal Rectangle“ erweitert das Histogrammproblem auf eine zweidimensionale binäre Matrix. Für jede Zeile berechnen Sie die kumulierten Balkenhöhen: Wenn matrix[row][col] == '1', ist die Höhe die Anzahl aufeinanderfolgender 1-Werte oberhalb und einschließlich dieser Zelle. Wenden Sie dann den Algorithmus für das „größte Rechteck im Histogramm“ auf das Höhenarray jeder Zeile an. Laufzeit: O(m × n) für eine m×n-Matrix.
def maximalRectangle(matrix):
if not matrix or not matrix[0]:
return 0
n = len(matrix[0])
heights = [0] * n
result = 0
def largest_in_hist(h):
h = h + [0]
stack, best = [], 0
for i, val in enumerate(h):
while stack and h[stack[-1]] > val:
height = h[stack.pop()]
left = stack[-1] + 1 if stack else 0
best = max(best, height * (i - left))
stack.append(i)
return best
for row in matrix:
for j, cell in enumerate(row):
heights[j] = heights[j] + 1 if cell == '1' else 0
result = max(result, largest_in_hist(heights[:]))
return result
m = [['1','0','1','0','0'],['1','0','1','1','1'],
['1','1','1','1','1'],['1','0','0','1','0']]
print(maximalRectangle(m)) # 6Regenwasser auffangen: Stack-Ansatz
LeetCode 42 „Trapping Rain Water“ mit einem Stack: Verwalten Sie einen fallenden Stack aus Indizes. Wenn ein höherer Balken gefunden wird, entsteht eine Mulde. Entfernen Sie den Boden der Mulde vom Stack; berechnen Sie die Breite des Wassers als (current_index - stack_top - 1) und die Höhe als (min(current_bar, new_stack_top_bar) - valley_height). Addieren Sie alle Beiträge. Zeit: O(n), Speicher: O(n).
def trap(height):
stack = []
water = 0
for i, h in enumerate(height):
while stack and height[stack[-1]] < h:
bottom = stack.pop()
if not stack:
break
left = stack[-1]
width = i - left - 1
bounded_h = min(h, height[left]) - height[bottom]
water += width * bounded_h
stack.append(i)
return water
print(trap([0,1,0,2,1,0,1,3,2,1,2,1])) # 6
print(trap([4,2,0,3,2,5])) # 9Monotone-Stack-Probleme erkennen
Signale dafür, dass ein monotoner Stack das richtige Werkzeug ist: Das Problem fragt nach dem nächstgrößeren oder nächstkleineren Element bzw. dem vorherigen größeren oder kleineren Element, das Ergebnis für jedes Element hängt von Elementen in einer bestimmten Richtung ab oder eine naive O(n²)-Lösung durchsucht für jedes Element die linke oder rechte Seite. Der Stack speichert Kandidaten, die für zukünftige Elemente Antworten sein könnten, und verwirft sie, sobald ein besserer Kandidat eintrifft.
Entscheiden Sie immer im Voraus: steigend (für das nächste oder vorherige kleinere Element) oder fallend (für das nächste oder vorherige größere Element) und in welcher Richtung Sie verarbeiten.
Amortisierte O(n)-Analyse
Monotone-Stack-Algorithmen wirken zunächst wie O(n log n) oder O(n²), weil sich innerhalb der for-Schleife eine while-Schleife befindet. Jedes Element wird jedoch höchstens einmal auf den Stack gelegt und höchstens einmal vom Stack entfernt. Die Gesamtzahl der push-Operationen beträgt n, und auch die Gesamtzahl der pop-Operationen ist höchstens n. Über alle Iterationen hinweg beträgt der Gesamtaufwand daher 2n Operationen – amortisiert O(n), nicht O(n²).
# Count total pushes and pops for n=1000
n = 1000
nums = list(range(n, 0, -1)) # worst case for decreasing stack
stack = []
pushes = pops = 0
for val in nums:
while stack and stack[-1] < val:
stack.pop()
pops += 1
stack.append(val)
pushes += 1
print(f'n={n}, pushes={pushes}, pops={pops}, total={pushes+pops}')
# Total <= 2*nZusammenfassung: Auswahl der Invariante für den monotonen Stack
Wählen Sie die Stack-Richtung anhand der Abfrage. Für das nächstgrößere Element verwenden Sie einen fallenden Stack – entfernen Sie Elemente, wenn das aktuelle Element größer ist. Für das nächstkleinere Element verwenden Sie einen steigenden Stack – entfernen Sie Elemente, wenn das aktuelle Element kleiner ist. Für das größte Rechteck verwenden Sie einen steigenden Stack und entfernen Elemente, wenn ein kürzerer Balken erscheint. Für das Maximum eines gleitenden Fensters verwenden Sie eine fallende Deque und entfernen Elemente an beiden Enden.
Wenn Sie die Invariante vor dem Programmieren in einem Kommentar notieren, wird die Logik klarer und das Debugging schneller.
Kurzer Test
Testen Sie Ihr Verständnis der Konzepte aus Data Structures & Algorithms — Coding Interview Prep aus dieser Lektion.
Zusammenfassung der Lektion
In dieser Lektion haben Sie Folgendes gelernt: Ein monotoner Stack bewahrt eine sortierte Invariante, indem er Elemente, die sie verletzen, vor dem Auflegen des neuen Elements entfernt, fallende Stacks beantworten Abfragen nach dem nächstgrößeren Element; steigende Stacks beantworten Abfragen nach dem nächstkleineren Element und die Gesamtlaufzeit beträgt amortisiert O(n), weil jedes Element höchstens einmal auf den Stack gelegt und entfernt wird. Als Nächstes implementieren wir Warteschlangen mit Stacks und Stacks mit Warteschlangen.
Häufig gestellte Fragen
Ist die Lektion „Muster des monotonen Stapels“ kostenlos?
Ja — der vollständige Text von „Muster des monotonen Stapels“ 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 „Muster des monotonen Stapels“?
Wenden Sie den monotonen Stapel an, um daily-temperatures, largest-rectangle-in-histogram und next-greater-element in O(n) zu lösen. 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 3 von 4.
Wie lange dauert die Lektion „Muster des monotonen Stapels“?
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
- Stapelimplementierung und Anwendungen
- Warteschlangenimplementierung und Deque
- Muster des monotonen Stapels
- Gegenseitige Simulation von Stapel und Warteschlange