🪟 Sliding Window – Cửa sổ trượt

🎯 Mục tiêu bài học

1. Đặt vấn đề

1.1. Cách làm trực tiếp

Với mỗi vị trí bắt đầu, cộng lại k phần tử. Có khoảng n cửa sổ, mỗi cửa sổ mất O(k), tổng O(nk).

1.2. Quan sát khi dịch cửa sổ

Khi cửa sổ [L,R] dịch sang phải thành [L+1,R+1]:

• Loại bỏ a[L].
• Thêm a[R+1].

Ta mở rộng R. Nếu tổng vượt K, tăng L để thu nhỏ cửa sổ cho đến khi hợp lệ.

2. Các dạng Sliding Window

3. Mô phỏng cửa sổ cố định

4. Mô phỏng cửa sổ co giãn

5. Sliding Window với bảng tần suất

Bài toán mẫu: tìm độ dài đoạn dài nhất có không quá K giá trị khác nhau.

6. Sliding Window Maximum bằng deque

Để lấy max mỗi cửa sổ trong O(1) trung bình, deque lưu chỉ số theo thứ tự giá trị giảm dần.

7. Phân tích thuật toán

8. Code mẫu

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    cin >> n >> k;

    vector<long long> a(n);
    for (long long &x : a) cin >> x;

    long long windowSum = 0;

    for (int i = 0; i < k; i++) {
        windowSum += a[i];
    }

    long long answer = windowSum;

    for (int right = k; right < n; right++) {
        windowSum += a[right];
        windowSum -= a[right - k];

        answer = max(answer, windowSum);
    }

    cout << answer;
}

int left = 0;
int best = 0;
long long sum = 0;

for (int right = 0; right < n; right++) {
    sum += a[right];

    while (left <= right && sum > k) {
        sum -= a[left];
        left++;
    }

    best = max(best, right - left + 1);
}

unordered_map<int,int> frequency;

int left = 0;
int distinct = 0;
int best = 0;

for (int right = 0; right < n; right++) {
    if (frequency[a[right]] == 0) {
        distinct++;
    }

    frequency[a[right]]++;

    while (distinct > k) {
        frequency[a[left]]--;

        if (frequency[a[left]] == 0) {
            distinct--;
        }

        left++;
    }

    best = max(best, right - left + 1);
}

deque<int> dq;

for (int i = 0; i < n; i++) {
    while (!dq.empty() && dq.front() <= i - k) {
        dq.pop_front();
    }

    while (!dq.empty() && a[dq.back()] <= a[i]) {
        dq.pop_back();
    }

    dq.push_back(i);

    if (i >= k - 1) {
        cout << a[dq.front()] << ' ';
    }
}

def max_sum_fixed_window(a, k):
    current = sum(a[:k])
    answer = current

    for right in range(k, len(a)):
        current += a[right]
        current -= a[right - k]
        answer = max(answer, current)

    return answer

9. Giải thích code

9.1. Vì sao cửa sổ cố định chỉ thêm một và bỏ một?

Khi dịch sang phải một vị trí, k−1 phần tử cũ vẫn nằm trong cửa sổ. Chỉ phần tử trái nhất rời đi và phần tử mới bên phải đi vào.

9.2. Vì sao while bên trong for vẫn O(n)?

9.3. Vì sao bài tổng ≤ K cần số không âm?

Nếu có số âm, khi tăng R tổng có thể giảm, và khi tăng L tổng có thể tăng. Khi đó quy tắc co cửa sổ không còn đúng.

9.4. Vì sao bảng tần suất cần giảm distinct khi count về 0?

Khi phần tử cuối cùng của một giá trị rời cửa sổ, giá trị đó không còn xuất hiện, nên số loại phải giảm.

9.5. Vì sao deque lưu chỉ số?

Cần biết phần tử nào đã ra khỏi cửa sổ. Chỉ số cho phép kiểm tra dq.front() <= i-k.

10. Lỗi thường gặp

• Nhầm cửa sổ đóng [L,R] với độ dài R-L+1.
• Quên trừ phần tử rời khỏi cửa sổ cố định.
• Dùng cửa sổ tổng ≤ K khi mảng có số âm.
• Co cửa sổ chỉ một lần bằng if thay vì while.
• Cập nhật đáp án trước khi cửa sổ hợp lệ.
• Quên giảm distinct khi tần suất về 0.
• Sliding Window Maximum lưu giá trị thay vì chỉ số.
• Điều kiện loại chỉ số cũ sai: đúng là dq.front() <= i-k.

11. Quiz và bài tập