Maximul fiecărei ferestre glisante
Ai o listă și o fereastră de lungime k care alunecă de la stânga la dreapta. Vrei maximul din fiecare fereastră. Forța brută este O(n·k). Cu un deque monoton de indici obții O(n), una dintre cele mai elegante soluții de interviu.
Problema
Pentru lista = [1, 3, -1, -3, 5, 3, 6, 7] și k = 3 sunt 6 ferestre:
Scrie funcția maxim_ferestre(lista, k) care returnează lista maximelor tuturor ferestrelor de lungime k, folosind un deque de indici, în O(n).
- Scoate din spatele deque-ului indicii cu valori <= x, apoi adaugă i.
- Scoate din față indicele ieșit din fereastră (coada[0] <= i - k) cu popleft().
- De la i >= k - 1 adaugă lista[coada[0]] în rezultat. Trebuie să apară: [3, 3, 5, 5, 6, 7], [9, 8, 7], [4, 4, 4, 4].
Restul explicațiilor, editorul și verificarea automată se deblochează cu Hash map, stive, cozi și liste înlănțuite.

Alex Cristian
Iulian Pahom
Catalina Ioana Dan