Monoton stack: næste større element
Besvar span-forespørgsler i én gennemløb
Monoton stack: næste større element er en gratis Forberedelse til kodeinterviews-lektion på CoddyKit. Dette er lektion 2 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.
Problemet med det næste større element
For hvert tal vil du finde den første større værdi til højre for det. Udtømmende søgning tager O(n i anden), men en monoton stak klarer det i én gennemgang.
Hvad monoton betyder
En monoton stak holder sine værdier i sorteret rækkefølge, her faldende, så vi ved, at vi har fundet et svar, så snart rækkefølgen ville blive brudt.
Gem indekser, ikke værdier
Skub indekser ind i stedet for selve tallene. På den måde ved du præcis, hvilken position der skal udfyldes, når et større element dukker op.
stack = []
ans = [-1] * len(nums)Gå fra venstre mod højre
Gennemløb arrayet én gang. Ved hvert indeks tager du enten afklarede elementer af stakken eller skubber det aktuelle indeks ind til senere.
for i in range(len(nums)):Tag de mindre elementer af
Så længe den aktuelle værdi er større end værdien ved det øverste indeks, har dette øverste element endelig fundet sit næste større element.
while stack and nums[i] > nums[stack[-1]]:Registrér svaret
Tag det øverste indeks af stakken, og sæt dets svar til den aktuelle værdi. Hvert indeks behandles præcis én gang, hvilket holder arbejdet lineært.
j = stack.pop()
ans[j] = nums[i]Skub ind, og fortsæt
Når du har behandlet alt, der er mindre, skal du skubbe det aktuelle indeks ind, så det kan vente på sit eget fremtidige større element.
stack.append(i)Rester har intet svar
Indekser, der stadig ligger på stakken til sidst, mødte aldrig en større værdi. De beholder deres standardværdi -1, hvilket betyder, at der ikke findes en sådan værdi.
Derfor er det O(n)
Hvert indeks bliver skubbet ind én gang og taget af én gang. Selv med den indre while-loop forbliver det samlede arbejde lineært over hele gennemgangen.
Vend det om for det næste mindre element
Har du i stedet brug for det næste mindre element? Hold stakken stigende ved at vende sammenligningen fra større end til mindre end.
while stack and nums[i] < nums[stack[-1]]:Et mønster, ikke et trick
Forespørgsler om intervaller, aktiekurser og histogramområder genbruger alle denne idé. Den monotone stak er et centralt konkurrencemønster, der er værd at lære udenad.
Hurtigt tjek
Du løser problemet med det næste større element ved hjælp af en monoton stak. Hvorfor er den samlede tidskompleksitet lineær?
Opsummering: Én gennemgang, mange svar
Du brugte en faldende monoton stak af indekser til at finde de næste større elementer i O(n). Det mønster åbner døren til mange problemer om intervaller. 🚀
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 “Monoton stack: næste større element” gratis?
Ja — hele teksten til “Monoton stack: næste større element” 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 “Monoton stack: næste større element”?
Besvar span-forespørgsler i én gennemløb 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 2 af 4.
Hvor lang tid tager lektionen “Monoton stack: næste større element”?
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
- Stakke til matchende parenteser
- Monoton stack: næste større element
- Køer og collections.deque
- Maksimum i et glidende vindue med deque