Maximalt värde i ett glidande fönster med deque
Håll reda på fönstrets extremvärden i O(n)
Maximalt värde i ett glidande fönster med deque är en gratis lektion i Förberedelse inför kodningsintervjuer på CoddyKit. Detta är lektion 4 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 Förberedelse inför kodningsintervjuer, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Det maximala värdet i ett glidande fönster
Givet en array och en fönsterstorlek k vill du hitta maximum för varje fönster när det glider åt höger. En naiv lösning tar O(n gånger k).
Ett snabbare löfte
Med en monoton deque kan du besvara varje fönster på totalt O(n)-tid genom att gå igenom arrayen bara en gång.
Spara index igen
Håll index i dequen i stället för värden. Med index kan du kontrollera om elementet längst fram har glidit ut ur det aktuella fönstret.
from collections import deque
dq = deque()
res = []Håll ordningen avtagande
Dequen hålls avtagande efter värde från framkant till bakkant, så indexet längst fram alltid pekar på fönstrets maximum.
Ta bort mindre element längst bak
Innan du lägger till index i tar du bort element från baksidan så länge deras värden är mindre, eftersom de aldrig kan bli ett framtida maximum.
while dq and nums[dq[-1]] <= nums[i]:
dq.pop()Lägg till det nya indexet
När de svagare elementen längst bak har tagits bort gör du append av det aktuella indexet. Dequens ordning förblir korrekt för nästa steg.
dq.append(i)Avlägsna den gamla framsidan
Om indexet längst fram hamnar utanför fönstret tar du bort det med popleft. Ett fönster med storleken k börjar på index i minus k plus ett.
if dq[0] <= i - k:
dq.popleft()Registrera varje maximum
När det första fullständiga fönstret bildas vid index k minus ett innehåller dequens framsida svaret för varje efterföljande position.
if i >= k - 1:
res.append(nums[dq[0]])Tänk på ordningen vid borttagning
Ta bort den gamla framsidan innan du läser svaret. Annars kan du rapportera ett maximum som redan har lämnat fönstret.
Varför linjär tid gäller
Varje index läggs till och tas bort högst en gång, så arbetet med dequen är amortiserat O(1) per steg och O(n) totalt.
Minimivärde i fönster, samma idé
För ett glidande fönsters minimum håller du dequen växande i stället. Vänd bara på jämförelsen när du beskär baksidan.
while dq and nums[dq[-1]] >= nums[i]:
dq.pop()Snabb kontroll
Vad innehåller den monotona dequens framsida vid beräkning av maximum i glidande fönster?
Sammanfattning: deque vinner över fönstret
Du höll en avtagande deque av index: ta bort små element längst bak, avlägsna den gamla framsidan och läs av framsidan för varje fönsters maximum på O(n)-tid. 🏆
Lär dig Förberedelse inför kodningsintervjuer 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
- 90
- Lektioner
- 360
Vanliga frågor
Är lektionen ”Maximalt värde i ett glidande fönster med deque” gratis?
Ja – hela texten till ”Maximalt värde i ett glidande fönster med deque” 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 Förberedelse inför kodningsintervjuer, kan Ni uppgradera till CoddyKit PRO. Kursen i Förberedelse inför kodningsintervjuer innehåller totalt 4 lektioner.
Vad lär jag mig i ”Maximalt värde i ett glidande fönster med deque”?
Håll reda på fönstrets extremvärden i O(n) Ni övar på Förberedelse inför kodningsintervjuer 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 Förberedelse inför kodningsintervjuer?
Du behöver inga förkunskaper. Utbildningen i Förberedelse inför kodningsintervjuer 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 4 av 4.
Hur lång tid tar lektionen ”Maximalt värde i ett glidande fönster med deque”?
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 Förberedelse inför kodningsintervjuer-lektionen?
Ja. Varje Förberedelse inför kodningsintervjuer-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