Monoton stack: nästa större element
Besvara intervallfrågor i ett enda varv
Monoton stack: nästa större element är en gratis lektion i Competitive Programming Academy på CoddyKit. Detta är lektion 2 av 4. Ni kan läsa hela lektionen gratis nedan och sedan öva praktiskt i webbläsaren med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt. Den ingår i lärvägen för Competitive Programming Academy, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i Competitive Programming Academy innehåller totalt 4 lektioner.
Problemet med nästa större element
För varje tal vill du hitta det första större värdet till höger. Brute force tar O(n i kvadrat), men en monoton stack löser det i ett enda genomlopp.
Vad monoton betyder
En monoton stack håller sina värden i sorterad ordning, här avtagande, så fort den ordningen skulle brytas vet vi att ett svar har hittats.
Spara index, inte värden
Lägg index på stacken i stället för själva talen. Då vet du exakt vilken position som ska fyllas när ett större element dyker upp.
stack = []
ans = [-1] * len(nums)Gå från vänster till höger
Iterera över arrayen en gång. Vid varje index tar du antingen bort element vars svar är klart eller lägger det aktuella indexet på stacken för senare.
for i in range(len(nums)):Ta bort de mindre
Så länge det aktuella värdet är större än värdet vid indexet på toppen har det indexet äntligen hittat sitt nästa större element.
while stack and nums[i] > nums[stack[-1]]:Registrera svaret
Ta bort indexet på toppen och sätt dess svar till det aktuella värdet. Varje index löses exakt en gång, vilket håller arbetet linjärt.
j = stack.pop()
ans[j] = nums[i]Lägg till och fortsätt
Efter att ha löst alla mindre element gör du push av det aktuella indexet, så att det kan vänta på sitt eget framtida större element.
stack.append(i)Rester saknar svar
Index som fortfarande finns på stacken i slutet träffade aldrig ett större värde. De behåller sitt standardvärde -1, vilket betyder att inget sådant värde finns.
Varför det är O(n)
Varje index läggs till en gång och tas bort en gång. Även med den inre while-loopen förblir det totala arbetet linjärt under hela genomloppet.
Vänd på det för nästa mindre
Behöver du i stället hitta nästa mindre element? Håll stacken växande genom att vända jämförelsen från större än till mindre än.
while stack and nums[i] < nums[stack[-1]]:Ett mönster, inte ett trick
Intervallfrågor, aktiekurser och histogramareor använder alla samma idé. Den monotona stacken är ett centralt tävlingsprogrammeringsmönster som är värt att lära sig utantill.
Snabb kontroll
Du löser problemet med nästa större element med en monoton stack. Varför är den totala tidskomplexiteten linjär?
Sammanfattning: ett genomlopp, många svar
Du använde en avtagande monoton stack av index för att hitta nästa större element på O(n)-tid. Det mönstret öppnar dörren till många intervallproblem. 🚀
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 ”Monoton stack: nästa större element” gratis?
Ja – hela texten till ”Monoton stack: nästa större element” kan läsas gratis här på webben. Om Ni vill öva interaktivt med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt och låsa upp resten av kursen i Competitive Programming Academy, kan Ni uppgradera till CoddyKit PRO. Kursen i Competitive Programming Academy innehåller totalt 4 lektioner.
Vad lär jag mig i ”Monoton stack: nästa större element”?
Besvara intervallfrågor i ett enda varv Ni övar på Competitive Programming Academy 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 Competitive Programming Academy?
Du behöver inga förkunskaper. Utbildningen i Competitive Programming Academy 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 2 av 4.
Hur lång tid tar lektionen ”Monoton stack: nästa större element”?
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 Competitive Programming Academy-lektionen?
Ja. Varje Competitive Programming Academy-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
- Stackar för matchande parenteser
- Monoton stack: nästa större element
- Köer och collections.deque
- Maximalt värde i ett glidande fönster med deque