De ce contează?
Te plimbi prin fața unui gard de scânduri de înălțimi diferite, privind printr-o fereastră dreptunghiulară care arată exact 3 scânduri o dată. La fiecare pas, fereastra alunecă o scândură mai la dreapta și tu vrei să spui repede: care e cea mai înaltă scândură vizibilă acum? Ar fi obositor să te uiți de fiecare dată la toate trei. Mai deștept: ții minte doar scândurile care încă ar putea fi „cea mai înaltă" pentru viitor — pe cele mărunte, ascunse după una mai înaltă deja intrată, le poți uita.
Intuiția
Ai un vector și o fereastră de lățime k care alunecă de la stânga la dreapta.
Pentru fiecare poziție a ferestrei vrei maximul elementelor din ea. Recalculul
brut e risipă: ferestrele vecine se suprapun aproape complet, deci reparcurgi mereu
aceleași valori. Ideea-cheie: ții o listă de candidați — elemente care încă pot
fi maxim — în ordine descrescătoare. Când intră un element mare, pe cei mai mici din
spatele listei îi arunci: ei nu mai pot câștiga niciodată. Maximul ferestrei e mereu
primul din listă. Pentru asta ai nevoie de o structură din care scoți de la ambele
capete: un deque.