Cấu trúc dữ liệu và Giải thuật Bài 22: Cửa sổ trượt (Sliding Window) kích thước cố định.

Ở bài học trước, chúng ta đã làm quen với kỹ thuật Hai con trỏ (Two Pointers) để tìm kiếm và lọc dữ liệu. Tuy nhiên, nếu bài toán không yêu cầu tìm một cặp phần tử rời rạc, mà yêu cầu phân tích một nhóm các phần tử nằm liền kề nhau có kích thước cố định, chúng ta sẽ cần đến một biến thể sắc bén hơn rất nhiều: Kỹ thuật Cửa sổ trượt (Sliding Window).

1. Hình tượng hóa "Cửa sổ trượt"

Hãy tưởng tượng bạn có một dải phim cuộn dài 100 bức ảnh. Bạn có một cái khung bìa cứng được đục một lỗ hình chữ nhật vừa vặn để nhìn thấy đúng 3 bức ảnh cùng lúc.

• Bạn đặt khung hình lên 3 bức ảnh đầu tiên (ảnh 0, 1, 2).

• Để xem 3 bức ảnh tiếp theo (ảnh 1, 2, 3), bạn không nhấc toàn bộ cái khung lên rồi đặt xuống lại. Bạn chỉ cần trượt cái khung sang phải 1 bước.

• Khi trượt, bức ảnh số 0 sẽ biến mất khỏi tầm nhìn (bị loại ra), và bức ảnh số 3 sẽ xuất hiện (được thêm vào). Hai bức ảnh 1 và 2 ở giữa vẫn giữ nguyên.

Đây chính xác là cách thuật toán Sliding Window hoạt động trong bộ nhớ máy tính.

2. Bài toán kinh điển: Mảng con kích thước K có tổng lớn nhất

Yêu cầu: Cho một mảng các số nguyên và một số nguyên dương $K$. Hãy tìm một mảng con liên tiếp gồm đúng $K$ phần tử có tổng lớn nhất.

Ví dụ: Mảng [2, 1, 5, 1, 3, 2], với $K = 3$.

• Các mảng con kích thước 3 là: [2,1,5], [1,5,1], [5,1,3], [1,3,2].

• Tổng lớn nhất là $5 + 1 + 3 = 9$.

Nỗi đau của Brute Force ($O(n \times K)$):

Cách tiếp cận ngây thơ là dùng một vòng lặp ngoài chạy dọc theo mảng, và một vòng lặp trong chạy $K$ bước để tính tổng lại từ đầu cho mỗi nhóm.

Nếu mảng có 1 triệu phần tử và $K = 100,000$, bạn sẽ phải thực hiện $1,000,000 \times 100,000$ phép cộng. CPU sẽ làm việc cực kỳ vất vả để tính đi tính lại những phần tử đã được tính ở bước trước đó.

3. Phép màu của Cửa sổ trượt ($O(n)$)

Thuật toán Sliding Window loại bỏ hoàn toàn sự lãng phí này bằng nguyên lý: Kế thừa kết quả của quá khứ.

1. Tính cửa sổ đầu tiên (Khởi tạo): Tính tổng của $K$ phần tử đầu tiên. Đây là nền tảng.

2. Trượt cửa sổ (Sliding): Từ phần tử thứ $K$ trở đi, để tính tổng của cửa sổ mới, bạn KHÔNG cần cộng lại $K$ phần tử. Bạn chỉ lấy tổng của cửa sổ cũ, trừ đi phần tử vừa bị bỏ lại phía sau (ở mép trái), và cộng thêm phần tử mới vừa bước vào (ở mép phải).

Mỗi lần dịch chuyển cửa sổ, bạn chỉ tốn đúng 2 phép toán (1 trừ, 1 cộng) — tức là $O(1)$. Duyệt qua toàn bộ mảng chỉ tốn $O(n)$.

4. Triển khai bằng Golang

Go

func maxSumSubarray(arr []int, k int) int {
    n := len(arr)
    if n < k {
        return 0 // Bắt lỗi: Kích thước mảng nhỏ hơn kích thước cửa sổ
    }
    
    // 1. Tính tổng của cửa sổ đầu tiên (từ index 0 đến K-1)
    currentSum := 0
    for i := 0; i < k; i++ {
        currentSum += arr[i]
    }
    
    maxSum := currentSum
    
    // 2. Bắt đầu trượt cửa sổ từ vị trí K đến cuối mảng
    for i := k; i < n; i++ {
        // Tổng mới = Tổng cũ - Phần tử mép trái (bị loại) + Phần tử mép phải (được thêm)
        // Mép trái bị loại có index là: i - k
        // Mép phải được thêm có index là: i
        currentSum = currentSum - arr[i-k] + arr[i]
        
        // Cập nhật kỷ lục nếu tổng mới lớn hơn
        if currentSum > maxSum {
            maxSum = currentSum
        }
    }
    
    return maxSum
}

• Phân tích với mảng [2, 1, 5, 1, 3, 2] và K = 3:

  • Khởi tạo cửa sổ đầu (index 0-2): 2 + 1 + 5 = 8. (maxSum = 8).

  • Trượt đến i = 3 (số 1): Trừ đi arr[0] (số 2), cộng thêm arr[3] (số 1). Tổng mới = 8 - 2 + 1 = 7.

  • Trượt đến i = 4 (số 3): Trừ đi arr[1] (số 1), cộng thêm arr[4] (số 3). Tổng mới = 7 - 1 + 3 = 9. (maxSum = 9).

  • Trượt đến i = 5 (số 2): Trừ đi arr[2] (số 5), cộng thêm arr[5] (số 2). Tổng mới = 9 - 5 + 2 = 6.

  • Kết quả trả về: 9.

5. Ứng dụng trong thiết kế hệ thống Backend

Tư duy Cửa sổ trượt kích thước cố định không chỉ là thuật toán để pass phỏng vấn, nó là nền tảng của hàng loạt cơ chế hệ thống thực tế:

• Rate Limiting (Giới hạn lưu lượng): Khi bạn dùng API của Google hay Facebook, họ có luật: "Mỗi IP chỉ được gọi tối đa 100 request trong 1 phút". Để kiểm soát việc này, backend sử dụng thuật toán Sliding Window Counter hoặc Sliding Window Log trong Redis để chặn đứng các cuộc tấn công DDoS hoặc bot spam. Cửa sổ thời gian $K$ chính là 60 giây.

• Xử lý dữ liệu Stream (Data Streaming): Khi theo dõi log server hoặc tín hiệu chứng khoán theo thời gian thực (Real-time), chúng ta thường cần tính "Trung bình động" (Moving Average) của 50 giao dịch gần nhất để vẽ biểu đồ trơn mượt hơn.

• Phân tích gói tin mạng (TCP Sliding Window): Giao thức TCP sử dụng chính xác cơ chế này để kiểm soát luồng dữ liệu (Flow Control). Nó gửi một "cửa sổ" gồm $K$ gói tin đi trước, khi nhận được phản hồi thành công của gói đầu tiên, cửa sổ mới tiếp tục trượt sang gói tiếp theo.

Bài toán Cửa sổ trượt kích thước cố định rất dễ hình dung vì chiếc khung hình của chúng ta không bị biến dạng. Nhưng thực tế thường nghiệt ngã hơn: Điều gì sẽ xảy ra nếu bài toán không cho trước $K$, mà yêu cầu bạn tự tìm ra một cái khung có kích thước thay đổi linh hoạt (lúc thì phình to, lúc thì thu nhỏ) để thỏa mãn một điều kiện hóc búa?