Patroon van de monotone stack
Pas de monotone stack toe om daily-temperatures, largest-rectangle-in-histogram en next-greater-element op te lossen in O(n).
Patroon van de monotone stack is een gratis DSA Interview Prep-les op CoddyKit. Dit is les 3 van 4. Je kunt 3 lessen uit dit leerpad gratis volledig lezen — daarna ontgrendelt CoddyKit PRO alle lessen, plus praktische oefeningen met een ingebouwde code-editor en een AI-tutor die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject DSA Interview Prep. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus DSA Interview Prep bevat in totaal 4 lessen.
Wat is een monotone stapel?
Een monotone stapel is een stapel die voor zijn elementen een sorteereigenschap handhaaft. Een oplopende monotone stapel bevat elementen die van onder naar boven oplopen; een aflopende monotone stapel bevat elementen die van onder naar boven aflopen. Wanneer een nieuw element de invariant schendt, worden elementen verwijderd totdat de invariant is hersteld, waarna het nieuwe element op de stapel wordt geplaatst.
Met dit eenvoudige mechanisme kun je in O(n) antwoorden vinden op vragen naar het 'dichtstbijzijnde grotere element' en het 'dichtstbijzijnde kleinere element', waarvoor je anders naïef geneste lussen van O(n²) nodig zou hebben.
# 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)Volgende grotere element (LeetCode 496)
Zoek voor elk element het eerste element rechts ervan dat strikt groter is. Een uitputtende oplossing van O(n²) scant vanaf elke positie naar rechts. De aanpak met een monotone stapel: houd een aflopende stapel met indexen bij. Wanneer je een groter element tegenkomt, verwijder je alle indexen van kleinere elementen — hun 'volgende grotere element' is het huidige element. De overgebleven indexen hebben geen volgend groter element (hun antwoord is -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]Volgende grotere element in een cirkelvormige array
LeetCode 503 'Next Greater Element II': hetzelfde probleem, maar de array wordt als cirkelvormig beschouwd. Nadat je het einde hebt bereikt, ga je terug naar het begin en controleer je de elementen daar. De truc is om twee keer door de array te lopen (indexen 0 tot 2n-1) en i % n te gebruiken om in de oorspronkelijke array te indexeren. Plaats alleen indexen in het bereik [0, n-1] op de stapel om dubbele verwerking te voorkomen.
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]Dagelijkse temperaturen: volledige oplossing
LeetCode 739 opnieuw bekeken: hoeveel dagen duurt het vanaf elke dag tot een warmere temperatuur? De monotone stapel bevat indexen van dagen met temperaturen in aflopende volgorde. Wanneer een warmere dag i wordt gevonden, verwijder je alle indexen j van koelere dagen van de stapel en leg je result[j] = i - j vast. Voor de dagen die op de stapel achterblijven, is nooit een warmere dag gevonden, dus hun resultaat blijft 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]Vorige kleinere element
De vraag naar het 'vorige kleinere element' luidt: wat is voor elk element de dichtstbijzijnde kleinere waarde links ervan? Gebruik een oplopende monotone stapel en verwerk de elementen van links naar rechts. Voordat je index i op de stapel plaatst, is de top van de stapel het vorige kleinere element, omdat alle elementen die groter zijn dan nums[i] al waren verwijderd bij eerdere toevoegingen.
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]Grootste rechthoek in een histogram
LeetCode 84 'Largest Rectangle in Histogram': gebruik een monotone oplopende stapel met indexen. Verwijder voor elke balk alle balken die hoger zijn dan de huidige balk. Voor elke verwijderde balk h is de rechtergrens de huidige index i en de linkergrens de nieuwe top van de stapel + 1 (of 0 als de stapel leeg is). Oppervlakte = h × (right - left). Voeg een schildwacht met hoogte 0 toe om alle overgebleven balken aan het einde te verwijderen.
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])) # 1Maximale rechthoek (LeetCode 85)
LeetCode 85 'Maximal Rectangle' breidt het histogramprobleem uit naar een 2D-binaire matrix. Bereken voor elke rij de opgetelde balkhoogten: als matrix[row][col] == '1', is de hoogte het aantal opeenvolgende en boven deze cel liggende enen. Pas vervolgens voor de hoogtenarray van elke rij het algoritme voor de 'grootste rechthoek in een histogram' toe. Tijd: O(m × n) voor een matrix van m×n.
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)) # 6Regenwater opvangen: aanpak met een stapel
LeetCode 42 'Trapping Rain Water' met een stapel: houd een aflopende stapel met indexen bij. Wanneer je een hogere balk tegenkomt, ontstaat er een dal. Verwijder de bodem van het dal; bereken de waterbreedte als (current_index - stack_top - 1) en de hoogte als (min(current_bar, new_stack_top_bar) - valley_height). Tel alle bijdragen bij elkaar op. Tijd: O(n), ruimte: 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-stapelproblemen herkennen
Signalen dat een monotone stapel het juiste hulpmiddel is: het probleem vraagt naar het volgende of vorige grotere/kleinere element, het antwoord voor elk element hangt af van elementen in een bepaalde richting, of een naïeve oplossing van O(n²) houdt in dat je voor elk element naar links of rechts scant. De stapel bewaart kandidaten die voor toekomstige elementen het antwoord kunnen zijn en verwijdert ze zodra er een betere kandidaat verschijnt.
Bepaal vooraf altijd: oplopend (voor het volgende of vorige kleinere element) of aflopend (voor het volgende of vorige grotere element), en vanuit welke richting je verwerkt.
Geamortiseerde O(n)-analyse
Monotone-stapelalgoritmen lijken in eerste instantie O(n log n) of O(n) te zijn omdat er een while-lus binnen de for-lus staat. Maar elk element wordt hoogstens eenmaal op de stapel geplaatst en hoogstens eenmaal verwijderd. Het totale aantal bewerkingen waarbij elementen worden geplaatst is n, en ook het totale aantal verwijderbewerkingen is hoogstens n. Over alle iteraties samen zijn er dus 2n bewerkingen — geamortiseerd O(n), niet 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*nSamenvatting: keuzes voor de invariant van een monotone stapel
Kies de richting van de stapel op basis van de vraag. Gebruik voor het volgende grotere element een aflopende stapel — verwijder elementen wanneer het huidige element groter is. Gebruik voor het volgende kleinere element een oplopende stapel — verwijder elementen wanneer het huidige element kleiner is. Gebruik voor de grootste rechthoek een oplopende stapel en verwijder elementen wanneer er een kortere balk verschijnt. Gebruik voor het maximum in een schuivend venster een aflopende deque en verwijder elementen aan beide uiteinden.
Schrijf de invariant vóór het programmeren in een opmerking; dat verduidelijkt de logica en versnelt het opsporen van fouten.
Korte toets
Toets je begrip van de concepten van Data Structures & Algorithms — Coding Interview Prep uit deze les.
Lesoverzicht
In deze les heb je geleerd: een monotone stapel handhaaft een sorteereigenschap door elementen die deze schenden te verwijderen voordat het nieuwe element wordt geplaatst, aflopende stapels beantwoorden vragen naar het volgende grotere element; oplopende stapels beantwoorden vragen naar het volgende kleinere element, en de totale tijd is geamortiseerd O(n), omdat elk element hoogstens eenmaal op de stapel wordt geplaatst en verwijderd. Hierna implementeren we wachtrijen met stapels en stapels met wachtrijen.
Leer Python met een AI-tutor — gratis
Schrijf echte code en voer die uit in je browser, krijg direct hulp van een AI-tutor die 24/7 beschikbaar is en ga verder waar je gebleven bent op het web of in de app.
- Cursussen
- 30
- Lessen
- 120
Veelgestelde vragen
Is de les “Patroon van de monotone stack” gratis?
Ja — je kunt hier op het web alle 3 lessen van het leerpad DSA Interview Prep, waaronder “Patroon van de monotone stack”, gratis volledig lezen. Daarna ontgrendelt CoddyKit PRO alle lessen, plus interactieve oefeningen met een ingebouwde code-editor en een AI-tutor die 24/7 beschikbaar is. De cursus DSA Interview Prep bevat in totaal 4 lessen.
Wat leer ik in “Patroon van de monotone stack”?
Pas de monotone stack toe om daily-temperatures, largest-rectangle-in-histogram en next-greater-element op te lossen in O(n). Je oefent met DSA Interview Prep door code rechtstreeks in de browser uit te voeren. Een AI-begeleider die 24/7 beschikbaar is beantwoordt je vragen terwijl je de les doorwerkt.
Heb ik ervaring nodig om met DSA Interview Prep te beginnen?
Ervaring vooraf is niet nodig. DSA Interview Prep op CoddyKit is opgebouwd voor beginners tot gevorderden, zodat je hier of bij het begin kunt starten en in je eigen tempo kunt leren. Dit is les 3 van 4.
Hoe lang duurt de les “Patroon van de monotone stack”?
De meeste lessen van CoddyKit duren ongeveer 5–10 minuten. Elke les is kort en interactief, zodat je gestaag vooruitgaat en op het web en in de app precies verdergaat waar je was gebleven.
Kan ik code schrijven en uitvoeren in deze les over DSA Interview Prep?
Ja. Elke les over DSA Interview Prep bevat een ingebouwde code-editor, zodat je rechtstreeks in je browser echte code kunt schrijven en uitvoeren en direct feedback van AI krijgt — lokale installatie is niet nodig.
Alle lessen in deze cursus
- Stackimplementatie en toepassingen
- Queue-implementatie en deque
- Patroon van de monotone stack
- Stack en queue wederzijds simuleren