Tổng quan
Kỹ thuật Cửa Sổ Trượt (Sliding Window) giải các bài toán về mảng con hoặc chuỗi con liền kề bằng cách duy trì một 'cửa sổ' trượt dọc theo dữ liệu. Thay vì tính lại kết quả cho từng cửa sổ từ đầu, nó tái sử dụng công sức của cửa sổ trước và chỉ điều chỉnh theo các phần tử đi vào và đi ra.
Với một cửa sổ kích thước cố định độ dài k — ví dụ, tìm mảng con có tổng lớn nhất kích thước k — việc tái sử dụng này biến cách tiếp cận ngây thơ O(n·k) thành một lượt duy nhất O(n). Duy trì một tổng cửa sổ chạy, cộng phần tử đi vào và trừ phần tử đi ra, chính là ý tưởng cốt lõi.
Cửa sổ trượt hoạt động thế nào?
- Cộng k phần tử đầu tiên để khởi tạo tổng cửa sổ, và ghi nhận nó là kết quả tốt nhất hiện tại.
- Trượt cửa sổ sang phải một vị trí bằng cách cộng phần tử mới đi vào ở bên phải.
- Trừ đi phần tử vừa rời khỏi cửa sổ ở bên trái, để tổng luôn đồng bộ trong O(1).
- So sánh tổng cửa sổ vừa cập nhật với kết quả tốt nhất đã thấy và cập nhật khi lớn hơn.
- Lặp lại đến khi cửa sổ chạm cuối mảng; kết quả tốt nhất đã ghi nhận chính là đáp án.
Khi nào nên dùng?
- Mảng con có tổng lớn nhất hoặc nhỏ nhất với kích thước cố định k — một bài phỏng vấn khởi động kinh điển.
- Tính trung bình trượt trên một luồng số liệu, chẳng hạn dữ liệu cảm biến hoặc giá cả.
- Các biến thể cửa sổ kích thước thay đổi: chuỗi con dài nhất không lặp ký tự, hay mảng con nhỏ nhất có tổng vượt một mục tiêu.
- Bất kỳ truy vấn trên đoạn liền kề nào mà các cửa sổ kề nhau chồng lấp nhiều và đáp án có thể cập nhật tăng dần.
Phân tích độ phức tạp
Mỗi phần tử đi vào cửa sổ một lần và rời đi một lần, và mỗi lần trượt là một phép cộng-và-trừ O(1), nên toàn bộ lượt quét là O(n) thời gian và O(1) bộ nhớ. Điều này vượt trội so với cách ngây thơ tính lại tổng cho từng cửa sổ trong n−k+1 cửa sổ một cách độc lập với chi phí O(k), tổng cộng thành O(n·k).
Câu hỏi thường gặp
Tổng chạy tránh việc tính lại như thế nào?
Hai cửa sổ liên tiếp chia sẻ tất cả trừ hai phần tử. Thay vì cộng lại toàn bộ k giá trị, bạn cộng phần tử vừa đi vào và trừ phần tử vừa đi ra — một cập nhật O(1) — nên tổng luôn cập nhật mà không cần quét lại.
Cửa sổ kích thước cố định và kích thước thay đổi khác nhau ra sao?
Cửa sổ kích thước cố định luôn trải đúng k phần tử, nên trượt bằng cách dịch cả hai cạnh cùng nhau. Cửa sổ kích thước thay đổi mở rộng cạnh phải để thỏa một điều kiện và thu nhỏ cạnh trái để giữ hợp lệ, phù hợp các bài như mảng con nhỏ nhất có tổng cho trước.
Cửa sổ trượt có hoạt động với số âm không?
Với cửa sổ kích thước cố định, tổng chạy hoạt động với mọi giá trị, kể cả số âm, vì nó chỉ đơn giản theo dõi tổng chính xác. Tuy nhiên, cửa sổ kích thước thay đổi vốn dựa vào việc thu nhỏ khi tổng lớn quá lại giả định giá trị không âm; với số âm bạn thường chuyển sang dùng tổng tiền tố (prefix sum) hoặc cách khác.