Maximum in een sliding window met deque
Uitersten van het venster in O(n) bijhouden
Maximum in een sliding window met deque is een gratis Voorbereiding op programmeerinterviews-les op CoddyKit. Dit is les 4 van 4. Je kunt de volledige les hieronder gratis lezen en daarna in de browser praktisch oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is. Deze les maakt deel uit van het leertraject Voorbereiding op programmeerinterviews. Je voortgang wordt gesynchroniseerd op het web en in de CoddyKit-app. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.
Het maximum van een schuifvenster
Gegeven een array en een venstergrootte k wil je het maximum van elk schuifvenster bepalen terwijl het naar rechts schuift. Naïef kost dit O(n maal k).
Een snellere belofte
Met een monotone deque kun je elk venster in totaal O(n) tijd verwerken door de array maar één keer te doorlopen.
Sla opnieuw indexen op
Bewaar indexen in de deque, geen waarden. Met indexen kun je controleren of het voorste element uit het huidige venster is geschoven.
from collections import deque
dq = deque()
res = []Houd de volgorde aflopend
De deque blijft op waarde aflopend van voor naar achter, zodat de voorste index altijd naar het maximum van het venster wijst.
Verwijder kleinere uiteinden
Verwijder voordat je index i toevoegt elementen aan de achterkant zolang hun waarden kleiner zijn, omdat ze nooit een toekomstig maximum kunnen zijn.
while dq and nums[dq[-1]] <= nums[i]:
dq.pop()De nieuwe index toevoegen
Nadat je de zwakkere uiteinden hebt verwijderd, voeg je de huidige index toe met append. De volgorde van de deque blijft correct voor de volgende stappen.
dq.append(i)Het verouderde voorste element verwijderen
Als de voorste index buiten het venster valt, verwijder je die met popleft. Een venster met grootte k begint op index i min k plus één.
if dq[0] <= i - k:
dq.popleft()Elk maximum vastleggen
Zodra het eerste volledige venster ontstaat op index k min één, bevat de voorkant van de deque vanaf dan het antwoord voor elke positie.
if i >= k - 1:
res.append(nums[dq[0]])Let op de volgorde van verwijderen
Verwijder het verouderde voorste element voordat je het antwoord leest. Anders rapporteer je misschien een maximum dat het venster al heeft verlaten.
Waarom de tijd lineair blijft
Elke index wordt hoogstens één keer toegevoegd en verwijderd. Daardoor kost het werk aan de deque geamortiseerd O(1) per stap en O(n) in totaal.
Minimumvenster, hetzelfde idee
Houd voor het minimum van een schuifvenster de deque in plaats daarvan oplopend. Draai bij het inkorten van de achterkant alleen de vergelijking om.
while dq and nums[dq[-1]] >= nums[i]:
dq.pop()Snelle controle
Wat bevat de voorkant van de monotone deque bij het maximum van een schuifvenster?
Samenvatting: deque wint bij vensters
Je hield een aflopende deque met indexen bij: verwijder kleine uiteinden, verwijder het verouderde voorste element en lees de voorkant voor het maximum van elk venster in O(n). 🏆
Leer Voorbereiding op programmeerinterviews met een AI-tutor — gratis
Schrijf echte code en voer die uit in je browser, krijg direct hulp van een AI-tutor die 24/7 beschikbaar is en ga verder waar je gebleven bent op het web of in de app.
- Cursussen
- 90
- Lessen
- 360
Veelgestelde vragen
Is de les “Maximum in een sliding window met deque” gratis?
Ja — de volledige tekst van “Maximum in een sliding window met deque” kun je hier gratis op het web lezen. Als je interactief wilt oefenen met een ingebouwde code-editor en een AI-begeleider die 24/7 beschikbaar is, en de rest van de cursus Voorbereiding op programmeerinterviews wilt ontgrendelen, kun je upgraden naar CoddyKit PRO. De cursus Voorbereiding op programmeerinterviews bevat in totaal 4 lessen.
Wat leer ik in “Maximum in een sliding window met deque”?
Uitersten van het venster in O(n) bijhouden Je oefent met Voorbereiding op programmeerinterviews door code rechtstreeks in de browser uit te voeren. Een AI-begeleider die 24/7 beschikbaar is beantwoordt je vragen terwijl je de les doorwerkt.
Heb ik ervaring nodig om met Voorbereiding op programmeerinterviews te beginnen?
Ervaring vooraf is niet nodig. Voorbereiding op programmeerinterviews op CoddyKit is opgebouwd voor beginners tot gevorderden, zodat je hier of bij het begin kunt starten en in je eigen tempo kunt leren. Dit is les 4 van 4.
Hoe lang duurt de les “Maximum in een sliding window met deque”?
De meeste lessen van CoddyKit duren ongeveer 5–10 minuten. Elke les is kort en interactief, zodat je gestaag vooruitgaat en op het web en in de app precies verdergaat waar je was gebleven.
Kan ik code schrijven en uitvoeren in deze les over Voorbereiding op programmeerinterviews?
Ja. Elke les over Voorbereiding op programmeerinterviews bevat een ingebouwde code-editor, zodat je rechtstreeks in je browser echte code kunt schrijven en uitvoeren en direct feedback van AI krijgt — lokale installatie is niet nodig.
Alle lessen in deze cursus
- Stacks voor overeenkomende haakjes
- Monotone stack: volgende grotere element
- Queues en collections.deque
- Maximum in een sliding window met deque