Sliding Window (fereastră glisantă)

Sliding Window este o tehnică în care menținem o “fereastră” de dimensiune fixă K care se deplasează prin vector, de la stânga la dreapta. La fiecare pas, un element intră în fereastră (pe dreapta) și unul iese (pe stânga).

Ideea de bază

Imaginați-vă o fereastră care “glisează” peste vector:

Vector:  3  1  4  1  5  9  2  6
         [-----]                    fereastra K=3: {3, 1, 4}  suma=8
            [-----]                 fereastra K=3: {1, 4, 1}  suma=6
               [-----]             fereastra K=3: {4, 1, 5}  suma=10
                  [-----]          fereastra K=3: {1, 5, 9}  suma=15
                     [-----]       fereastra K=3: {5, 9, 2}  suma=16
                        [-----]    fereastra K=3: {9, 2, 6}  suma=17

La fiecare pas:

• Adăugăm elementul nou (cel din dreapta)
• Scoatem elementul vechi (cel din stânga)

Nu recalculăm totul de la zero - doar actualizăm!

Problema 1: suma maximă pe fereastră de lungime K

Abordarea naivă (lentă)

Pentru fiecare poziție, calculăm suma a K elemente:

// O(n * K) - lent!
for (int i = 1; i + k - 1 <= n; i++) {
    int suma = 0;
    for (int j = i; j < i + k; j++) {
        suma += v[j];
    }
    // ...
}

Cu Sliding Window (rapid)

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int v[100001];
int n, k;

int main()
{
    fin >> n >> k;
    for (int i = 1; i <= n; i++) {
        fin >> v[i];
    }

    // Suma primei ferestre
    int suma = 0;
    for (int i = 1; i <= k; i++) {
        suma = suma + v[i];
    }

    int maxSuma = suma;
    int pozMax = 1;

    // Glisăm fereastra
    for (int i = 2; i + k - 1 <= n; i++) {
        suma = suma + v[i + k - 1] - v[i - 1];
        //          ^adaugam noul     ^scoatem vechiul

        if (suma > maxSuma) {
            maxSuma = suma;
            pozMax = i;
        }
    }

    fout << "Suma maxima: " << maxSuma << endl;
    fout << "Pozitia: " << pozMax;

    return 0;
}

date.in:

8 3
3 1 4 1 5 9 2 6

date.out:

Suma maxima: 17
Pozitia: 6

Pas cu pas (K = 3)

Formula cheie

suma_noua = suma_veche + v[i + k - 1] - v[i - 1]

Adăugăm elementul care intră și scădem elementul care iese. O singură adunare și o scădere, indiferent de cât de mare este K.

Problema 2: media maximă pe fereastră de K elemente

Identic cu suma maximă, dar împărțim la K la final:

// Dupa ce gasim maxSuma:
double mediaMax = (double)maxSuma / k;
fout << mediaMax;

Problema 3: câte ferestre de lungime K au suma mai mare decât S?

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int v[100001];
int n, k, s;

int main()
{
    fin >> n >> k >> s;
    for (int i = 1; i <= n; i++) {
        fin >> v[i];
    }

    int suma = 0;
    for (int i = 1; i <= k; i++) {
        suma = suma + v[i];
    }

    int cnt = 0;
    if (suma > s) cnt++;

    for (int i = 2; i + k - 1 <= n; i++) {
        suma = suma + v[i + k - 1] - v[i - 1];
        if (suma > s) cnt++;
    }

    fout << cnt;

    return 0;
}

date.in:

8 3 10
3 1 4 1 5 9 2 6

date.out:

3

Ferestrele cu suma > 10: {4,1,5}=10 (nu), {1,5,9}=15 (da), {5,9,2}=16 (da), {9,2,6}=17 (da).

Problema 4: minimul din fiecare fereastră

Vrem minimul din fiecare fereastră de K elemente. Aceasta este mai complexă - nu putem actualiza minimul cu o singură operație ca la sumă.

Varianta simplă (O(n * K))

for (int i = 1; i + k - 1 <= n; i++) {
    int minim = v[i];
    for (int j = i + 1; j <= i + k - 1; j++) {
        if (v[j] < minim) minim = v[j];
    }
    fout << minim << " ";
}

Varianta cu recalculare parțială

Când elementul care iese din fereastră nu era minimul, minimul rămâne la fel. Când era minimul, recalculăm:

#include <fstream>
using namespace std;
ifstream fin("date.in");
ofstream fout("date.out");

int v[100001];
int n, k;

int main()
{
    fin >> n >> k;
    for (int i = 1; i <= n; i++) {
        fin >> v[i];
    }

    for (int i = 1; i + k - 1 <= n; i++) {
        int minim = v[i];
        for (int j = i + 1; j <= i + k - 1; j++) {
            if (v[j] < minim) minim = v[j];
        }
        fout << minim << " ";
    }

    return 0;
}

date.in:

8 3
3 1 4 1 5 9 2 6

date.out:

1 1 1 1 2 2

Sliding Window vs Sume Parțiale

Ambele rezolvă probleme cu “ferestre” de lungime K, dar în moduri diferite:

• Sume parțiale: când ai nevoie de sumă pe orice interval, nu neapărat consecutive
• Sliding window: când procesezi ferestre consecutive de lungime fixă

Greșeli frecvente

1. Recalcularea întregii sume la fiecare pas

// GREȘIT (lent):
for (int i = 1; i + k - 1 <= n; i++) {
    int suma = 0;
    for (int j = i; j < i + k; j++) suma += v[j]; // recalculam tot!
}

// CORECT (rapid):
suma = suma + v[i + k - 1] - v[i - 1]; // doar actualizam

2. Indicii greșiți la glisare

// Elementul care INTRA in fereastra: v[i + k - 1]
// Elementul care IESE din fereastra: v[i - 1]

Dacă încurci ordinea sau indicii, suma devine greșită.

3. Prima fereastră calculată greșit

Prima fereastră trebuie calculată separat (suma de la 1 la K). Glisarea începe de la a doua fereastră (i = 2).

4. Limita buclei de glisare

// GRESIT:
for (int i = 2; i <= n; i++) { // depaseste vectorul cand i + k - 1 > n

// CORECT:
for (int i = 2; i + k - 1 <= n; i++) { // ne asiguram ca fereastra incape

Ce să reții

• Sliding Window glisează o fereastră de K elemente prin vector.
• La fiecare pas: adăugăm un element, scoatem altul.
• Suma: suma = suma + v[nou] - v[vechi] - O(1) per pas.
• Complexitate: O(n) în loc de O(n * K).
• Prima fereastră se calculează separat.
• Util pentru: suma maximă/minimă pe K elemente, medie, numărare.
• Pentru min/max pe fereastră, varianta simplă este O(n * K).

Probleme

pbinfoNr Max De Zerouri→