Mønsteret med monoton stack
Anvend en monoton stack til at løse daily-temperatures, largest-rectangle-in-histogram og next-greater-element i O(n).
Mønsteret med monoton stack er en gratis Forberedelse til kodeinterviews-lektion på CoddyKit. Dette er lektion 3 af 4. Du kan læse hele lektionen gratis nedenfor — og derefter øve dig praktisk i browseren med en indbygget kodeeditor og en AI-vejleder, der er tilgængelig døgnet rundt. Den er en del af læringsforløbet i Forberedelse til kodeinterviews, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Hvad er en monoton stak
En monoton stak er en stak, der opretholder en sorteret invariant blandt sine elementer. En stigende monoton stak har elementer, der stiger fra bund til top, mens en faldende monoton stak har elementer, der falder fra bund til top. Når et nyt element overtræder invarianten, fjernes elementer, indtil invarianten er genoprettet, hvorefter det nye element lægges på stakken.
Denne enkle mekanisme gør det muligt at besvare forespørgsler om det 'nærmeste større element' og det 'nærmeste mindre element' i O(n), selv om en naiv løsning ville kræve indlejrede løkker i O(n²).
# 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æste større element (LeetCode 496)
Find for hvert element det første element til højre, som er strengt større. En udtømmende O(n²)-løsning gennemløber elementerne mod højre fra hver position. Med den monotone stak opretholder du en faldende stak af indekser. Når et større element mødes, fjernes alle indekser for mindre elementer — deres 'næste større element' er det aktuelle element. De resterende indekser har intet næste større element (svaret er -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æste større element i et cirkulært array
LeetCode 503 'Next Greater Element II': Det samme problem, men arrayet behandles som cirkulært. Når du når slutningen, går du tilbage til begyndelsen og fortsætter undersøgelsen. Tricket er at gennemløbe arrayet to gange (indekserne 0 til 2n-1) og bruge i % n til at indeksere det oprindelige array. Læg kun indekser i området [0, n-1] på stakken for at undgå at behandle dem flere gange.
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]Daglige temperaturer: komplet løsning
LeetCode 739 igen: Hvor mange dage går der for hver dag, før temperaturen bliver højere? Den monotone stak indeholder indekser for dage med temperaturer i faldende rækkefølge. Når der findes en varmere dag i, fjernes alle indekser j for koldere dage fra stakken, og result[j] = i - j registreres. Dage, der er tilbage i stakken, fandt aldrig en varmere dag, så deres resultat forbliver 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]Forrige mindre element
Forespørgslen om det 'forrige mindre element' spørger: Hvad er den nærmeste mindre værdi til venstre for hvert element? Brug en stigende monoton stak, som behandles fra venstre mod højre. Før du lægger indeks i på stakken, er stakkens top det forrige mindre element, fordi alle elementer, der var større end nums[i], allerede blev fjernet under tidligere indsættelser, hvor større elementer fik dem fjernet.
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ørste rektangel i et histogram
LeetCode 84 'Largest Rectangle in Histogram': Brug en monoton stigende stak af indekser. For hver søjle fjernes alle søjler, der er højere end den aktuelle. For hver fjernet søjle h er den højre grænse det aktuelle indeks i, og den venstre grænse er den nye staktop + 1 (eller 0, hvis stakken er tom). Areal = h × (højre - venstre). Tilføj en vagtværdi med højden 0 for at tvinge alle resterende søjler ud af stakken til sidst.
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])) # 1Maksimalt rektangel (LeetCode 85)
LeetCode 85 'Maximal Rectangle' udvider histogramproblemet til en todimensional binær matrix. For hver række beregner du de akkumulerede søjlehøjder: Hvis matrix[row][col] == '1', er højden antallet af sammenhængende 1-taller over og inklusive denne celle. Anvend derefter algoritmen for det største rektangel i et histogram på hver rækkes højderarray. Tidsforbrug: O(m × n) for en matrix på 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)) # 6Opsamling af regnvand: stakmetoden
LeetCode 42 'Trapping Rain Water' med en stak: Oprethold en faldende stak af indekser. Når en højere søjle mødes, dannes en dal. Fjern dalens bund, og beregn vandets bredde som (current_index - stack_top - 1) og højden som (min(current_bar, new_stack_top_bar) - valley_height). Læg alle bidrag sammen. Tidsforbrug: O(n), pladsforbrug: 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])) # 9Genkendelse af problemer med monotone stakke
Tegn på, at en monoton stak er det rette værktøj: Problemet spørger efter det næste eller forrige større/mindre element, svaret for hvert element afhænger af elementer i en bestemt retning, eller en naiv O(n²)-løsning indebærer, at du gennemløber mod venstre eller højre for hvert element. Stakken gemmer kandidater, der muligvis er svar for fremtidige elementer, og kasserer dem, så snart en bedre kandidat dukker op.
Beslut altid på forhånd, om stakken skal være stigende (for næste/forrige mindre element) eller faldende (for næste/forrige større element), og fra hvilken retning du vil behandle elementerne.
Amortiseret O(n)-analyse
Monotone stakalgoritmer ser først ud til at være O(n log n) eller O(n²), fordi der er en while-løkke inde i en for-løkke. Men hvert element lægges på højst én gang og fjernes højst én gang. Det samlede antal indsættelser er n, og det samlede antal fjernelser er også højst n. På tværs af alle gennemløb er det samlede arbejde derfor 2n operationer — amortiseret O(n), ikke 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*nOpsummering: valg af invariant for monoton stak
Vælg stakkens retning ud fra forespørgslen. For næste større element skal du bruge en faldende stak — fjern elementer, når det aktuelle element er større. For næste mindre element skal du bruge en stigende stak — fjern elementer, når det aktuelle element er mindre. For største rektangel skal du bruge en stigende stak og fjerne elementer, når en kortere søjle dukker op. For maksimum i et glidende vindue skal du bruge en faldende deque og fjerne elementer fra begge ender.
Skriv invarianten i en kommentar, før du koder. Det tydeliggør logikken og gør fejlfinding hurtigere.
Hurtigt tjek
Afprøv din forståelse af begreberne fra Data Structures & Algorithms — Coding Interview Prep i denne lektion.
Opsummering af lektionen
I denne lektion lærte du: en monoton stak opretholder en sorteret invariant ved at fjerne elementer, der overtræder den, før det nye element lægges på stakken, faldende stakke besvarer forespørgsler om næste større element, mens stigende stakke besvarer forespørgsler om næste mindre element, og det samlede tidsforbrug er O(n) amortiseret, fordi hvert element højst lægges på og fjernes én gang. Dernæst implementerer vi køer ved hjælp af stakke og stakke ved hjælp af køer.
Lær Forberedelse til kodeinterviews med en AI-underviser — gratis
Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.
- Kurser
- 90
- Lektioner
- 360
Ofte stillede spørgsmål
Er lektionen “Mønsteret med monoton stack” gratis?
Ja — hele teksten til “Mønsteret med monoton stack” kan læses gratis her på nettet. Hvis du vil øve dig interaktivt med en indbygget kodeeditor og en AI-vejleder døgnet rundt og få adgang til resten af Forberedelse til kodeinterviews-kurset, skal du opgradere til CoddyKit PRO. Forberedelse til kodeinterviews-kurset indeholder 4 lektioner i alt.
Hvad lærer jeg i “Mønsteret med monoton stack”?
Anvend en monoton stack til at løse daily-temperatures, largest-rectangle-in-histogram og next-greater-element i O(n). Du øver dig i Forberedelse til kodeinterviews med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.
Skal jeg have erfaring for at begynde på Forberedelse til kodeinterviews?
Der kræves ingen tidligere erfaring. Forberedelse til kodeinterviews på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 3 af 4.
Hvor lang tid tager lektionen “Mønsteret med monoton stack”?
De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.
Kan jeg skrive og køre kode i denne Forberedelse til kodeinterviews-lektion?
Ja. Alle Forberedelse til kodeinterviews-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.
Alle lektioner i dette kursus
- Implementering og anvendelse af stacks
- Implementering af kø og deque
- Mønsteret med monoton stack
- Gensidig simulering af stack og kø