Mönstret monoton stack
Tillämpa en monoton stack för att lösa daily-temperatures, largest-rectangle-in-histogram och next-greater-element i O(n).
Mönstret monoton stack är en gratis lektion i DSA Interview Prep på CoddyKit. Detta är lektion 3 av 4. Du kan läsa vilka 3 lektioner som helst i den här lärvägen kostnadsfritt i sin helhet – därefter låser CoddyKit PRO upp alla lektioner, plus praktisk övning med en inbyggd kodredigerare och en AI-lärare dygnet runt. Den ingår i lärvägen för DSA Interview Prep, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i DSA Interview Prep innehåller totalt 4 lektioner.
Vad är en monoton stack?
En monoton stack är en stack som upprätthåller en sorterad invariant bland sina element. En stigande monoton stack har element som ökar från botten till toppen, medan en fallande monoton stack har element som minskar från botten till toppen. När ett nytt element bryter mot invarianten tas element bort tills invarianten har återställts, och därefter läggs det nya elementet till.
Denna enkla mekanism gör det möjligt att i O(n) besvara frågor om 'närmaste större element' och 'närmaste mindre element', som naivt skulle kräva O(n²) nästlade loopar.
# 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ästa större element (LeetCode 496)
För varje element ska du hitta det första elementet till höger som är strikt större. En brute force-lösning i O(n²) söker åt höger från varje position. Lösningen med monoton stack: upprätthåll en fallande stack med index. När ett större element hittas tas alla mindre index bort – deras 'nästa större element' är det aktuella elementet. Kvarvarande index har inget nästa större element (svaret är -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ästa större element i en cirkulär array
LeetCode 503 'Next Greater Element II': samma problem, men arrayen behandlas som cirkulär. När slutet nås går du runt och kontrollerar från början. Tricket är att iterera genom arrayen två gånger (index 0 till 2n-1) och använda i % n för att indexera den ursprungliga arrayen. Lägg bara till index i intervallet [0, n-1] för att undvika dubbel bearbetning.
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]Dagliga temperaturer: fullständig lösning
LeetCode 739 igen: för varje dag, hur många dagar dröjer det innan temperaturen blir varmare? Den monotona stacken innehåller index för dagar med temperaturer i fallande ordning. När en varmare dag i hittas tas alla index j för svalare dagar bort från stacken, och result[j] = i - j registreras. Dagar som finns kvar i stacken hittade aldrig en varmare dag, så deras resultat förblir 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]Föregående mindre element
Frågan om 'föregående mindre element' lyder: vilket är det närmaste mindre värdet till vänster om varje element? Använd en stigande monoton stack och bearbeta elementen från vänster till höger. Innan index i läggs till är stackens topp det föregående mindre elementet, eftersom alla element som är större än nums[i] redan togs bort under tidigare insättningar.
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]Största rektangeln i ett histogram
LeetCode 84 'Largest Rectangle in Histogram': en monoton stigande stack med index. För varje stapel tas alla staplar som är högre än den aktuella bort. För varje borttagen stapel h är den högra gränsen det aktuella indexet i och den vänstra gränsen stackens nya topp + 1 (eller 0 om stacken är tom). Area = h × (right - left). Lägg till en sentinel med höjden 0 för att tvinga fram borttagningen av alla återstående staplar i slutet.
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])) # 1Maximal rektangel (LeetCode 85)
LeetCode 85 'Maximal Rectangle' utökar histogramproblemet till en tvådimensionell binär matris. För varje rad beräknar du de ackumulerade stapelhöjderna: om matrix[row][col] == '1' är höjden antalet sammanhängande ettor ovanför och inklusive denna cell. Tillämpa sedan algoritmen för 'största rektangeln i ett histogram' på varje rads höjdarray. Tidskomplexitet: O(m × n) för en m×n-matris.
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)) # 6Samla regnvatten: stackmetoden
LeetCode 42 'Trapping Rain Water' med en stack: upprätthåll en fallande stack med index. När en högre stapel hittas bildas en sänka. Ta bort sänkans botten och beräkna vattnets bredd som (current_index - stack_top - 1) och höjden som (min(current_bar, new_stack_top_bar) - valley_height). Summera alla bidrag. Tid: O(n), utrymme: 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])) # 9Att känna igen problem med monotona stackar
Tecken på att en monoton stack är rätt verktyg: problemet frågar efter nästa eller föregående större/mindre element, svaret för varje element beror på element i en viss riktning, eller en naiv O(n²)-lösning innebär att man söker åt vänster eller höger för varje element. Stacken lagrar kandidater som kan vara svar för framtida element och tar bort dem så snart en bättre kandidat kommer.
Bestäm alltid i förväg om du ska använda en stigande stack (för nästa/föregående mindre element) eller en fallande stack (för nästa/föregående större element), samt från vilket håll elementen ska bearbetas.
Amortiserad O(n)-analys
Monotona stackalgoritmer kan först verka vara O(n log n) eller O(n²) eftersom while-loopen ligger inuti for-loopen. Men varje element läggs till högst en gång och tas bort högst en gång. Det totala antalet lägg-till-operationer är n, och det totala antalet borttagningsoperationer är också högst n. Därför är det totala arbetet över alla iterationer 2n operationer – amortiserat O(n), inte 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*nSammanfattning: val av invariant för monotona stackar
Välj stackens riktning utifrån frågan. För nästa större element använder du en fallande stack – ta bort element när det aktuella elementet är större. För nästa mindre element använder du en stigande stack – ta bort element när det aktuella elementet är mindre. För största rektangeln använder du en stigande stack och tar bort element när en kortare stapel visas. För maximum för ett glidande fönster använder du en fallande deque och tar bort element från båda ändarna.
Att skriva invarianten i en kommentar innan kodningen klargör logiken och gör felsökningen snabbare.
Snabbtest
Testa din förståelse av koncepten i Data Structures & Algorithms — Coding Interview Prep från den här lektionen.
Sammanfattning av lektionen
I den här lektionen lärde du dig: en monoton stack upprätthåller en sorterad invariant genom att ta bort element som bryter mot den innan det nya elementet läggs till, fallande stackar besvarar frågor om nästa större element, medan stigande stackar besvarar frågor om nästa mindre element och den totala tidskomplexiteten är O(n) amortiserat eftersom varje element läggs till och tas bort högst en gång. Härnäst implementerar vi köer med stackar och stackar med köer.
Lär dig Python med en AI-lärare – gratis
Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.
- Kurser
- 30
- Lektioner
- 120
Vanliga frågor
Är lektionen ”Mönstret monoton stack” gratis?
Ja – du kan läsa vilka 3 lektioner som helst i lärvägen DSA Interview Prep, inklusive ”Mönstret monoton stack”, kostnadsfritt i sin helhet här på webben. Därefter låser CoddyKit PRO upp alla lektioner, plus interaktiv övning med en inbyggd kodredigerare och en AI-lärare dygnet runt. Kursen i DSA Interview Prep innehåller totalt 4 lektioner.
Vad lär jag mig i ”Mönstret monoton stack”?
Tillämpa en monoton stack för att lösa daily-temperatures, largest-rectangle-in-histogram och next-greater-element i O(n). Ni övar på DSA Interview Prep med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.
Behöver jag någon erfarenhet för att börja lära mig DSA Interview Prep?
Du behöver inga förkunskaper. Utbildningen i DSA Interview Prep på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 3 av 4.
Hur lång tid tar lektionen ”Mönstret monoton stack”?
De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.
Kan jag skriva och köra kod i den här DSA Interview Prep-lektionen?
Ja. Varje DSA Interview Prep-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.
Alla lektioner i den här kursen
- Implementering och användning av stackar
- Implementering av köer och deque
- Mönstret monoton stack
- Ömsesidig simulering av stack och kö