Sliding window — thống kê trên cửa sổ trượt

TL;DR: Hãy tưởng tượng bạn nhìn qua khung cửa sổ một con tàu đang chạy — lúc nào bạn cũng chỉ thấy N cảnh gần nhất, cảnh cũ trôi khỏi khung khi cảnh mới lọt vào. Cửa sổ trượt (sliding window) là kỹ thuật trả lời câu hỏi "tình hình ra sao trong N phần tử gần nhất?" mà không phải nhìn lại từ đầu mỗi lần. Có ba mẹo tuỳ loại câu hỏi: muốn biết phần tử lớn nhất / nhỏ nhất trong khung thì xếp một hàng "người cao đứng trước" (monotonic deque); muốn tìm đoạn dài nhất thoả điều kiện về tổng thì dùng hai con trỏ co giãn khung (two-pointer); muốn đếm xem trong khung có bao nhiêu loại phần tử khác nhau thì đếm tần suất bằng bảng tra (hash map). Cả ba đều nhanh vì mỗi phần tử chỉ vào khung một lần rồi ra một lần.

Hệ thống monitoring của Cloudflare phải tính độ trễ lớn nhất trong 60 giây gần nhất trên mỗi node biên (edge node), cập nhật mỗi giây. Nếu cứ mỗi giây lại quét lại cả cửa sổ: 60 phép mỗi node × 10.000 node × 1 lần/giây = 600.000 phép/giây — tạm chấp nhận được. Nhưng nếu cửa sổ kéo dài 1 giờ (3.600 giây), vẫn 10.000 node, mỗi giây quét lại: 3.600 × 10.000 × 1 = 36 triệu phép/giây — không kham nổi. Mấu chốt: quét lại cả cửa sổ mỗi bước là lãng phí, vì hai cửa sổ liền nhau gần như giống hệt.

Monotonic deque giải quyết bài này với O(1) amortized cho mỗi update và O(1) cho query, bất kể kích thước cửa sổ.

1. Trực giác — khung cửa sổ con tàu đang chạy

Trước khi vào định nghĩa, hãy hình dung bạn ngồi trên một con tàu đang chạy và nhìn ra ngoài qua một khung cửa sổ. Lúc nào bạn cũng chỉ thấy N cảnh gần nhất: khi tàu tiến lên, một cảnh mới lọt vào mép phải của khung, đồng thời cảnh cũ nhất trôi ra khỏi mép trái. Cửa sổ trượt làm đúng vậy trên dữ liệu: một "khung" gồm N phần tử liên tiếp, dịch dần sang phải khi dữ liệu mới tới.

Giả sử bạn muốn biết: "cảnh cao nhất (ngọn núi cao nhất) đang trong khung lúc này là gì?" Cách ngây thơ là mỗi lần khung dịch lại nhìn quét hết N cảnh từ đầu — chậm, vì làm lại công việc cũ. Có một mẹo hay hơn: xếp một hàng "người cao đứng trước". Mỗi khi một cảnh mới vào khung, ai trong hàng thấp hơn nó thì bị loại (vì còn có người vừa cao hơn vừa mới hơn, người thấp kia không bao giờ là cao nhất nữa). Nhờ vậy đầu hàng luôn là cảnh cao nhất đang trong khung — chỉ cần liếc đầu hàng, không quét lại gì. Hàng đặc biệt này về sau gọi là monotonic deque (hàng đợi đơn điệu hai đầu).

2. Bài toán tổng quát

Cho mảng (hoặc stream) A[0..n-1] và cửa sổ kích thước k. Với mỗi vị trí r từ k-1 đến n-1, cần tính thống kê trên A[r-k+1 .. r].

Hai từ trong bảng cần làm rõ ngay: prefix sum (tổng tích luỹ) là mảng cộng dồn — prefix[i] lưu tổng mọi phần tử từ đầu tới i, nhờ vậy tổng của một đoạn bất kỳ tính ngay bằng một phép trừ thay vì cộng lại từng phần tử. "Nhanh tuyến tính" nghĩa là tổng công việc tỉ lệ thuận với số phần tử n (ký hiệu O(n)): xử lý gấp đôi dữ liệu thì tốn gấp đôi thời gian, không hơn.

Cấu trúc dữ liệu cốt lõi là deque (double-ended queue, hàng đợi hai đầu): thêm/bớt ở cả hai đầu đều tức thì — chi tiết ở bài queue và deque.

3. Kỹ thuật 1 — Monotonic deque cho sliding max

Hợp khi nào: bạn cần phần tử lớn nhất (hoặc nhỏ nhất) trong một khung kích thước cố định trượt đều — đúng kiểu "hỏi ngọn núi cao nhất đang trong khung". Đây là lúc dùng hàng "người cao đứng trước" (monotonic deque, hàng đợi đơn điệu hai đầu).

3.1 Ý tưởng

Giữ một deque chứa chỉ số (index) các phần tử đang là ứng viên max cho cửa sổ hiện tại. "Ứng viên" theo nghĩa: nếu một phần tử vừa nhỏ hơn vừa cũ hơn một phần tử khác trong cửa sổ, nó sẽ không bao giờ là max — vì luôn có người vừa cao hơn vừa ở lại lâu hơn. Đúng như hàng "người cao đứng trước": mỗi khi nạp phần tử mới, ta loại (pop) khỏi deque những ai thấp hơn nó, giữ deque giảm dần.

Deque lúc nào cũng thỏa A[deque[0]] ≥ A[deque[1]] ≥ ..., nên max của cửa sổ hiện tại luôn là phần tử ở đầu deque, A[deque[0]] — chỉ cần liếc đầu hàng.

3.2 Pseudocode

function slidingWindowMax(A, k):
    -- Trả về mảng max[i] = max của A[i-k+1 .. i], i từ k-1 đến n-1
    DQ <- empty deque     -- lưu chỉ số, giảm dần theo giá trị
    result <- []

    for r <- 0 to A.length - 1:
        -- Bước 1: loại chỉ số ngoài cửa sổ (phần tử quá cũ)
        while DQ không rỗng và DQ.front() < r - k + 1:
            DQ.pop_front()

        -- Bước 2: loại chỉ số nhỏ hơn A[r] từ phía sau (không còn là ứng viên)
        while DQ không rỗng và A[DQ.back()] <= A[r]:
            DQ.pop_back()

        DQ.push_back(r)

        -- Bước 3: sau khi cửa sổ đủ k phần tử, ghi nhận max
        if r >= k - 1:
            result.append(A[DQ.front()])

    return result
// Time: O(n)  Space: O(k)

3.3 Trace — A = [3, 1, 2, 5, 4], k = 3

Kết quả: [3, 5, 5] — đúng với cửa sổ [3,1,2], [1,2,5], [2,5,4].

Bước r = 3 pop ba lần, nhìn như phản ví dụ cho O(1) mỗi bước. Thật ra nó là bằng chứng: cả ba chỉ số đó đều đã được nạp ở bước trước, và mỗi chỉ số chỉ trả giá ra đúng một lần trong cả hành trình.

4. Vì sao monotonic deque chạy nhanh?

Mấu chốt nằm ở chỗ: mỗi chỉ số r chỉ vào deque đúng một lần và ra đúng một lần (hoặc bị loại ở bước 1 vì đã trôi khỏi cửa sổ, hoặc ở bước 2 vì có phần tử cao hơn đẩy ra). Một vòng lặp đơn lẻ đôi khi loại nhiều phần tử cùng lúc, nhìn có vẻ chậm — nhưng những phần tử đó từng được nạp vào trước đó, mỗi phần tử chỉ "trả giá ra" một lần trong cả hành trình. Vì vậy tổng công việc cho cả mảng tỉ lệ với n, không phải n nhân kích thước cửa sổ.

Cách tính "trung bình mỗi thao tác tốn bao nhiêu khi xét cả chuỗi thao tác" này gọi là amortized (phân tích khấu hao): tổng O(n) chia đều cho n lần cập nhật ra O(1) mỗi lần — xem amortized analysis.

5. Kỹ thuật 2 — Two-pointer cho subarray thoả điều kiện

Hợp khi nào: bạn cần tìm một đoạn liên tiếp dài nhất (hoặc ngắn nhất) thoả một điều kiện về tổng — ví dụ "đoạn dài nhất có tổng không vượt một ngưỡng". Hình dung hai con trỏ như hai mép khung co giãn được: kéo mép phải ra để gom thêm, kéo mép trái vào khi đã quá đà.

Hình dung một cái kẹp co giãn: bạn nới mép phải ra để gom thêm phần tử, rồi siết mép trái vào ngay khi đoạn vừa gom vượt điều kiện. Hai con trỏ l (mép trái) và r (mép phải) đều chỉ chạy về phía trước, không bao giờ lùi. Kéo r ra để mở rộng cửa sổ; co l vào khi cửa sổ vi phạm điều kiện.

Two-pointer hợp nhất với mảng mà mọi phần tử không âm: lúc đó nới mép phải luôn làm tổng tăng, siết mép trái luôn làm tổng giảm — tính chất "đi một chiều" này (gọi là monotone, tức biến đổi đơn điệu theo một hướng) chính là thứ cho phép hai con trỏ không cần quay lui.

5.1 Bài toán: subarray dài nhất có sum ≤ target

function longestSubarraySumAtMost(A, target):
    l <- 0
    currentSum <- 0
    maxLen <- 0

    for r <- 0 to A.length - 1:
        currentSum <- currentSum + A[r]    -- mở rộng cửa sổ sang phải

        -- Thu hẹp từ trái khi vi phạm
        while currentSum > target:
            currentSum <- currentSum - A[l]
            l <- l + 1

        -- Cửa sổ [l..r] hợp lệ
        maxLen <- max(maxLen, r - l + 1)

    return maxLen
// Time: O(n)  Space: O(1)

Nhanh vì cả l lẫn r chỉ đi tới (không bao giờ lùi), mỗi con trỏ tiến tối đa n bước, nên tổng công việc tỉ lệ thuận với số phần tử.

5.2 Bài toán: đoạn dài nhất không lặp ký tự

Bài này thêm một bảng tra (hash map) — bảng cho phép tra "ký tự này xuất hiện gần nhất ở vị trí nào" tức thì, để biết khi nào một ký tự bị lặp lại bên trong cửa sổ:

function longestUniqueSubstring(S):
    lastSeen <- Map()       -- ký tự → chỉ số xuất hiện gần nhất
    l <- 0
    maxLen <- 0

    for r <- 0 to S.length - 1:
        c <- S[r]
        if c trong lastSeen và lastSeen[c] >= l:
            -- Ký tự lặp lại trong cửa sổ — dịch l sang sau nó
            l <- lastSeen[c] + 1
        lastSeen[c] <- r
        maxLen <- max(maxLen, r - l + 1)

    return maxLen
// Time: O(n)  Space: O(alphabet_size)

Trace S = "abcab":

Kết quả: 3 ("abc" hoặc "bca" hoặc "cab").

6. Kỹ thuật 3 — Cửa sổ cố định + HashMap cho distinct

Hợp khi nào: bạn cần đếm có bao nhiêu loại phần tử khác nhau trong khung (distinct), hoặc kiểm tra ràng buộc về tần suất. Mẹo: giữ một bảng tra (hash map) "loại phần tử → đếm bao nhiêu cái trong khung", cộng thêm khi phần tử lọt vào mép phải, trừ bớt khi phần tử rời mép trái — số loại có đếm lớn hơn 0 chính là số phần tử khác nhau.

Hình dung một quầy điểm danh ở cửa khung: mỗi phần tử lọt vào mép phải thì cộng một vạch vào tên loại của nó; mỗi phần tử rời mép trái thì xoá một vạch. Số loại còn ít nhất một vạch chính là số phần tử khác nhau — không cần đếm lại cả khung mỗi bước. Dưới đây là cách đếm số phần tử khác nhau (distinct, tức số loại khác nhau) trong cửa sổ kích thước k cố định:

function slidingWindowDistinct(A, k):
    freq <- Map()          -- phần tử → số lần xuất hiện trong cửa sổ
    distinct <- 0
    result <- []

    for r <- 0 to A.length - 1:
        -- Thêm A[r] vào cửa sổ
        freq[A[r]] <- freq.getOrDefault(A[r], 0) + 1
        if freq[A[r]] = 1: distinct <- distinct + 1    -- lần đầu xuất hiện

        -- Loại A[r-k] ra khi cửa sổ đã đủ k+1
        if r >= k:
            out <- A[r - k]
            freq[out] <- freq[out] - 1
            if freq[out] = 0: distinct <- distinct - 1    -- biến mất khỏi cửa sổ

        if r >= k - 1:
            result.append(distinct)

    return result
// Time: O(n)  Space: O(k)

7. Khi nào dùng kỹ thuật nào

Dấu hiệu nhận biết bài sliding window: đề hỏi về "subarray liên tiếp", "cửa sổ N phần tử gần nhất", "dài nhất/ngắn nhất thoả [điều kiện trên tập liên tiếp]".

8. Pitfall

Pitfall 1 — Deque lưu giá trị thay vì chỉ số

-- SAI: lưu giá trị vào deque
DQ.push_back(A[r])          -- Không biết khi nào phần tử ra khỏi cửa sổ!
if DQ.front() < A[r-k]: DQ.pop_front()   -- So sánh giá trị sai

-- DUNG: lưu chỉ số, kiểm tra out-of-window bằng chỉ số
DQ.push_back(r)
while DQ.front() < r - k + 1: DQ.pop_front()   -- so sánh index

Deque phải lưu chỉ số để kiểm tra chính xác khi nào phần tử ra ngoài cửa sổ. Lưu giá trị mất thông tin vị trí — không phân biệt được A[i] = A[j] ở hai vị trí khác nhau.

Pitfall 2 — Dùng two-pointer khi điều kiện không biến đổi một chiều (không monotone)

-- SAI: dùng two-pointer cho "subarray có tổng = target" với A gồm âm và dương
-- Khi thu hẹp l, tổng có thể tăng hoặc giảm không đoán trước được
-- → two-pointer không đảm bảo tìm đủ mọi cửa sổ hợp lệ

-- DUNG với A gồm cả số âm: dùng prefix sum + HashMap
prefix[0] <- 0
for i <- 1 to n: prefix[i] <- prefix[i-1] + A[i-1]
-- Tìm i, j sao cho prefix[j] - prefix[i] = target
-- tương đương tìm prefix[i] = prefix[j] - target trong HashMap

Two-pointer chỉ đúng khi mảng không âm (hoặc khi điều kiện biến đổi một chiều — cửa sổ lớn hơn thì luôn càng vi phạm hoặc luôn càng hợp lệ, chứ không lúc thế này lúc thế kia).

Pitfall 3 — Quên điều kiện biên khi l vượt r

-- SAI: khi target rất nhỏ, l có thể vượt r trong while loop
while currentSum > target:
    currentSum <- currentSum - A[l]
    l <- l + 1
-- Sau loop, l > r → cửa sổ rỗng, nhưng vẫn tính r - l + 1 = âm

-- DUNG: giới hạn l không vượt r+1, hoặc kiểm tra kích thước cửa sổ
while currentSum > target và l <= r:
    currentSum <- currentSum - A[l]
    l <- l + 1
if l <= r: maxLen <- max(maxLen, r - l + 1)

Khi tất cả phần tử đơn lẻ đều lớn hơn target, mọi cửa sổ đều vi phạm — kết quả là 0, không phải âm.

9. Liên hệ các bài khác

• Queue và deque: Monotonic deque là ứng dụng trực tiếp của deque — cần hiểu push/pop hai đầu O(1) mới thấy vì sao sliding max chạy O(n). Đọc bài đó để nắm cấu trúc trước khi học kỹ thuật này.
• Amortized analysis: Lập luận "mỗi phần tử vào deque đúng 1 lần, ra đúng 1 lần → tổng O(n)" là phân tích amortized. Bài đó cung cấp công cụ chứng minh chính thức cho lập luận này.
• Count-Min Sketch: bài trước trong module. Ghép cửa sổ trượt với Count-Min Sketch (cấu trúc ước lượng tần suất tốn ít bộ nhớ) cho ta mẫu "cửa sổ thời gian + đếm tần suất gần đúng": dùng hai sketch luân phiên, mỗi nửa cửa sổ đổi vai, để giới hạn số request theo thời gian. Cần hiểu cả hai kỹ thuật mới dựng được mẫu này.
• HyperLogLog: tương tự, ghép HyperLogLog (cấu trúc ước lượng số phần tử khác nhau cực tiết kiệm bộ nhớ) với cửa sổ trượt cho câu hỏi "có bao nhiêu người dùng khác nhau trong 5 phút gần nhất" — rất hay gặp trên bảng phân tích (analytics dashboard).
• Mini-challenge top-K: bài thực hành — ghép monotonic deque (hoặc heap) với cửa sổ trượt để tìm K phần tử nổi bật nhất trên một luồng dữ liệu (stream).

📚 Deep Dive

Tóm tắt

• Sliding window duy trì một cửa sổ trên mảng/stream và cập nhật kết quả khi cửa sổ dịch — tránh tính lại từ đầu.
• Monotonic deque cho sliding max/min: giữ deque giảm dần (chỉ số), pop back khi phần tử mới lớn hơn, pop front khi ngoài cửa sổ. Max = A[deque.front()]. O(n) tổng, O(1) amortized mỗi phép.
• Two-pointer cho sum/điều kiện: mở rộng r, thu hẹp l — chỉ đúng khi điều kiện monotone với kích thước cửa sổ (mảng không âm hoặc điều kiện tương đương).
• HashMap + sliding cho distinct: tăng/giảm freq khi thêm/xoá phần tử, đếm distinct từ số entry có freq lớn hơn 0.
• Dấu hiệu nhận biết: "subarray/substring liên tiếp", "N phần tử gần nhất", "dài nhất/ngắn nhất thoả [điều kiện trên tập liên tiếp]".

Tự kiểm tra

Bài tiếp theo: Mini-challenge — top-K phần tử trên stream