O alta idee de rezolvare se bazeaza pe faptul ca pentru a trece de la secventa care incepe pe pozitia $i$ la cea care incepe pe pozitia $i+1$ dispare elementul de pe pozitia $i$ si apare unul nou pe pozitia $i+K$. Pornind de la aceasta observatie, putem folosi un 'heap':problema/heapuri pentru a efectua stergerile si inserarile in complexitate $O(logN)$ si pentru a afla minimul pentru un interval in $O(1)$. In acest caz, complexitatea totala este $O(NlogN)$ si o astfel de abordare ar trebui sa obtina $60$ de puncte [sursa 'aici':job_detail/229674]. Este posibil ca folosind diverse optimizari, aceasta rezolvare sa obtina $100$ puncte (motivul principal fiind cantitatea datelor de intrare).

Solutia optima, in complexitate $O(N)$, foloseste o coada cu doua capete ({$double ended queue, deque$}). In aceasta structura, valorile noi pot fi inserate doar la sfarsitul cozii, in timp ce elementele existente pot fi eliminate atat pe la inceputul, cat si pe la sfarsitul deque-ului; toate aceste operatii avand loc in timp constant. Se observa ca daca exista doua elemente $A[j] &ge; A[i]$ cu $j < i$, atunci $A[i]$ va fi mereu preferat pentru minim fata de $A[j]$, pentru secventele ce incep dupa pozitia $i$ (inclusiv). Din acest motiv, la fiecare pas $i$, elementul curent $A[i]$ elimina de la finalul $deque$-ului toate elementele $&ge;$ cu el, apoi este inserat la finalul cozii. In acest fel, elementele din $deque$ sunt mentinute in ordine crescatoare, deci minimul se va afla la inceput. Se elimina minimul cat timp acesta nu mai apartine secventei curente (pozitia lui este $&le; i-K$). In final, se aduna minimul la solutie. O implementare a acestei structuri de date se gaseste 'aici':job_detail/229406?action=view-source.

Solutia optima, in complexitate $O(N)$, foloseste o coada cu doua capete ({$double ended queue, deque$}). In aceasta structura, valorile noi pot fi inserate doar la sfarsitul cozii, in timp ce elementele existente pot fi eliminate atat pe la inceputul, cat si pe la sfarsitul $deque$-ului; toate aceste operatii avand loc in timp constant. Se observa ca daca exista doua elemente $A[j] &ge; A[i]$ cu $j < i$, atunci $A[i]$ va fi mereu preferat pentru minim fata de $A[j]$, pentru secventele ce incep dupa pozitia $i$ (inclusiv). Din acest motiv, la fiecare pas $i$, elementul curent $A[i]$ elimina de la finalul $deque$-ului toate elementele $&ge;$ cu el, apoi este inserat la finalul cozii. In acest fel, elementele din $deque$ sunt mentinute in ordine crescatoare, deci minimul se va afla la inceput. Se elimina minimul cat timp acesta nu mai apartine secventei curente (pozitia lui este $&le; i-K$). In final, se aduna minimul la solutie. O implementare a acestei structuri de date se gaseste 'aici':job_detail/229406?action=view-source.

h2. Aplicatii

Aceasta structura de date poate fi adaptata intr-o larga varietate de probleme. In

Aceasta structura de date poate fi adaptata intr-o larga varietate de probleme. In special, $deque$-ul poate fi aplicat in probleme de programare dinamica, cand trebuie determinat minimul/maximul unei functii pe un interval ce se deplaseaza treptat. De asemenea, cu ajutorul acestei structuri de date, pot fi rezolvate si urmatoarele probleme:

* 'Secventa':problema/secventa
* 'Vila2':problema/vila2