Maximul fiecărei ferestre cu deque, în C++

Ferestrele de lungime 3 din 1 3 -1 -3 5 3 au maximele 3 3 5 5. O fereastră este un interval de poziții consecutive. Dacă recalculezi maximul parcurgând toate cele k elemente la fiecare pas, poți ajunge la O(n·k) operații.

Coada dublă păstrează numai candidați

Un deque, prescurtare de la double-ended queue, este o coadă dublă: permite adăugări și eliminări la ambele capete. Păstrăm indici, nu doar valori, pentru a ști când un element a ieșit din fereastră. Indicii cresc de la început la sfârșit, iar valorile corespunzătoare descresc strict.

Citim 1≤k≤n≤1000 și n întregi. Afișăm n-k+1 maxime, în ordinea ferestrelor. Tabloul clasic rezervă 1000 de celule, din care n sunt folosite. Indicii interni pornesc de la zero.

Două eliminări cu motive diferite

La poziția i, fereastra completă începe la i-k+1. Indicii cel mult i-k sunt expirați și ies din fața cozii. Apoi scoatem din spate orice candidat cu valoare cel mult a[i]: noua valoare este cel puțin la fel de bună și va rămâne în ferestre mai mult timp.

Adăugăm i în spate. După primele k valori, maximul este mereu valoarea indicelui din față. Înainte de acel moment nu afișăm nimic, deoarece fereastra nu este încă întreagă.

Pentru 1,3,-1,-3,5,3, cele patru ferestre de lungime 3 au maximele 3,3,5,5, în ordinea începuturilor.Mărește schema ↗

Varianta cu tablou clasic

#include <iostream>
#include <deque>
using namespace std;
int main() {
    int n,k; cin >> n >> k;
    int a[1000];
    for(int i=0;i<n;++i) cin >> a[i];
    deque<int> q; bool primul=true;
    for(int i=0;i<n;++i) {
        while(!q.empty() && q.front()<=i-k) q.pop_front();
        while(!q.empty() && a[q.back()]<=a[i]) q.pop_back();
        q.push_back(i);
        if(i>=k-1) {
            cout << (primul?"":" ") << a[q.front()]; primul=false;
        }
    }
    cout << '\n';
}

Varianta echivalentă cu std::vector

Păstrăm limitele intrării și aceleași rezultate. Tabloul clasic rezervă capacitatea maximă; vectorul construiește numărul de elemente necesare. Indicii folosiți de algoritm rămân aceiași.

#include <vector>

#include <iostream>
#include <deque>
using namespace std;
int main() {
    int n,k; cin >> n >> k;
    vector<int> a(n);
    for(int i=0;i<n;++i) cin >> a[i];
    deque<int> q; bool primul=true;
    for(int i=0;i<n;++i) {
        while(!q.empty() && q.front()<=i-k) q.pop_front();
        while(!q.empty() && a[q.back()]<=a[i]) q.pop_back();
        q.push_back(i);
        if(i>=k-1) {
            cout << (primul?"":" ") << a[q.front()]; primul=false;
        }
    }
    cout << '\n';
}

Urmărește înlocuirea unui maxim

La sosirea valorii 3 din exemplu, 1 este eliminat din spate: nu mai poate câștiga o fereastră care o conține și pe 3. Valorile -1 și -3 rămân temporar candidați. Când apare 5, ele sunt eliminate împreună cu vechii candidați mai mici, iar 5 devine noul maxim.

front() și back() citesc indicii de la capete; pop_front() și pop_back() îi elimină. Verificăm empty() înainte de acces. Nu confundăm operațiile cozii cu eliminarea datelor din vector: a rămâne neschimbat.

Fiecare indice este introdus o dată și eliminat cel mult o dată. Timpul total este O(n), iar coada folosește O(k) memorie. Intrarea memorată ocupă separat O(n). Folosirea unor valori negative nu afectează argumentul bazat pe comparații.

Exersează

Pentru k=1 afișezi chiar vectorul. Pentru k=n afișezi un singur maxim. Testează toate valorile egale, valori strict crescătoare și valori strict descrescătoare. Pentru -5 -2 -7, k=2, rezultatul este -2 -2.

Continuă cu cozi și stive, maxime și secvențe.

Întrebări frecvente

Ce este un deque în algoritmul maximului pe fereastră?

Un deque este o coadă dublă, cu operații la ambele capete. Algoritmul păstrează în ea indici de candidați la maxim, ordonați astfel încât primul să ofere maximul ferestrei curente.

De ce nu păstrăm numai valorile candidaților?

Indicele arată când un candidat a ieșit din fereastră. Doar valoarea nu este suficientă, mai ales când există duplicate. Elementele expirate se elimină din fața cozii.

Cum obținem toate maximele ferestrelor în O(n)?

Fiecare indice intră o singură dată în deque și este eliminat cel mult o dată. Eliminările de la ambele capete sunt astfel O(n) în total, iar memoria auxiliară este O(k).