Cửa sổ trượt — Sliding Window
Cửa sổ trượt duy trì một đoạn con liên tiếp (subarray hoặc substring) và trượt nó dọc theo dữ liệu, mỗi bước chỉ cập nhật trạng thái trong O(1) thay vì tính lại toàn bộ từ đầu.
Có hai dạng: cửa sổ cố định độ dài k, và cửa sổ co giãn theo điều kiện (mở rộng bên phải, co bên trái khi vi phạm). Mấu chốt giúp đạt O(n) là mỗi phần tử chỉ vào và ra khỏi cửa sổ tối đa một lần.
Tưởng tượng bạn ngồi trên xe khách nhìn ra cửa sổ.
- Cửa sổ luôn cho thấy đúng K mét đường, xe chạy thì khung trượt theo.
- Bạn không phải nhìn lại 1 km vừa qua — chỉ nhìn cửa sổ hiện tại.
Dấu hiệu nhận biết
Gặp những từ khoá này trong đề → nghĩ ngay đến Cửa sổ trượt
| Từ khoá trong đề | Tại sao gợi đến chủ đề này |
|---|---|
| đoạn con liên tiếp | Subarray / substring cố định hoặc co dãn |
| tổng / max / min của K | Cửa sổ cố định K phần tử |
| longest substring thoả điều kiện | Cửa sổ co dãn theo điều kiện |
| cửa sổ không trùng | Set theo dõi ký tự đang trong cửa sổ |
Khi nào dùng
3 tình huống điển hình cần nghĩ đến chủ đề này
Cần duyệt mọi đoạn liên tiếp độ dài K trong mảng/chuỗi
Tính max/min/sum của các đoạn cố định hoặc đoạn thoả điều kiện
Tránh tính lại từ đầu mỗi lần (O(n·k) → O(n))
Khi nào KHÔNG dùng
3 tình huống chủ đề này không phù hợp — biết để tránh overuse
Bài cần xét subarray rời rạc (non-contiguous): không phải Sliding Window
Điều kiện cửa sổ không monotone theo size: window co-giãn sai → quay lại brute-force hoặc DP
Cần truy cập phần tử bên ngoài cửa sổ: Sliding Window mất tính chất O(n)
Hình minh hoạ
Chỉnh dữ liệu rồi bấm Phát để xem từng bước.
// Tổng lớn nhất của cửa sổ K phần tử liên tiếplet windowSum = 0, maxSum = 0for (let r = 0; r < k; r++) windowSum += nums[r] // build initialmaxSum = windowSum // first windowfor (let r = k; r < nums.length; r++) { // slidewindowSum += nums[r] - nums[r - k]maxSum = Math.max(maxSum, windowSum)}
Code mẫu
Hầu hết bài cùng chủ đề dùng chung mẫu này — copy rồi điền phần logic riêng của bài.
function slidingWindow(nums: T[], k: number): R {
let left = 0
let windowState = initState()
for (let right = 0; right < nums.length; right++) {
// 1. Mở rộng cửa sổ: thêm nums[right] vào windowState
expand(windowState, nums[right])
// 2. Co cửa sổ nếu vi phạm điều kiện
while (!isValid(windowState)) {
shrink(windowState, nums[left])
left++
}
// 3. Cập nhật answer dựa trên cửa sổ hợp lệ
answer = best(answer, windowState)
}
return answer
}Recap
Tổng hợp nhanh — đọc lại trước phỏng vấn
Điểm chính
Duy trì 2 con trỏ left và right tạo thành cửa sổ
Khi mở rộng: tăng right, cập nhật state
Khi thu hẹp: tăng left, gỡ phần tử khỏi state
Mỗi phần tử chỉ được visit tối đa 2 lần → O(n)
Lỗi thường gặp
Quên cập nhật state khi shrink cửa sổ (gỡ phần tử left ra khỏi count/sum)
Dùng
ifthay vìwhilekhi thu hẹp cửa sổ biến đổi — phải co liên tục tới khi cửa sổ hợp lệDùng cửa sổ cố định khi đề thực ra cần cửa sổ biến đổi (và ngược lại)
Độ phức tạp
Time O(n), Space O(1) hoặc O(k) tuỳ trạng thái lưu trữBài luyện theo chủ đề này
Phân theo độ khó — luyện tuần tự cho chắc tay