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

TL;DR: Cửa sổ trượt (sliding window) là kỹ thuật duy trì một tập con các phần tử liên tiếp trong mảng/stream và trả lời truy vấn trên tập đó khi cửa sổ dịch sang phải. Ba kỹ thuật chính: (1) Monotonic deque cho max/min trong O(1) amortized — giữ deque giảm dần, pop khi phần tử mới lớn hơn hoặc ngoài cửa sổ; (2) Two-pointer cho sum/điều kiện — mở rộng phải khi chưa đủ, thu hẹp trái khi vượt; (3) HashMap + deque cho distinct. Tất cả đều đạt O(n) tổng nhờ mỗi phần tử vào deque/pointer đúng một lần và ra đúng một lần.

Hệ thống monitoring của Cloudflare phải tính max latency trong 60 giây gần nhất trên mỗi trong số hàng nghìn edge node, cập nhật mỗi giây. Nếu quét lại toàn bộ cửa sổ mỗi giây: O(60) mỗi node × 10.000 node × 1 update/giây = 600.000 ops/giây — chấp nhận được. Nhưng khi cửa sổ là 1 giờ (3.600 giây) với 100 node/giây, chi phí tăng lên 360 triệu ops/giây.

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. 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].

Cấu trúc dữ liệu cốt lõi — deque (double-ended queue) — là liên kết trực tiếp tới bài queue và deque: push/pop cả hai đầu O(1).

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

2.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: phần tử nhỏ hơn phần tử mới hơn (index lớn hơn) trong cửa sổ sẽ không bao giờ là max — vì phần tử đó vừa nhỏ hơn vừa sẽ ra khỏi cửa sổ trước. Ta pop chúng ra khỏi deque khi nạp phần tử mới, giữ deque giảm dần.

Deque lúc nào cũng thỏa A[deque[0]] ≥ A[deque[1]] ≥ ... → max cửa sổ hiện tại luôn là A[deque[0]].

2.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)

Vì sao O(n)? Mỗi chỉ số r được push vào deque đúng 1 lần và pop ra đúng 1 lần (hoặc ở bước 1 do out-of-window, hoặc ở bước 2 do bị phần tử lớn hơn đẩy ra). Tổng số phép pop không vượt tổng số phép push = n. Đây là phân tích amortized: tổng chi phí O(n) dù mỗi vòng lặp có thể pop nhiều lần — xem amortized analysis.

2.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].

flowchart LR
    subgraph "r=2: nạp A[2]=2"
        D0["DQ: [0,1]"]
        POP["pop back: A[1]=1 ≤ 2"]
        D1["DQ: [0,2]"]
        MAX1["max = A[0] = 3"]
        D0 --> POP --> D1 --> MAX1
    end
    subgraph "r=3: nạp A[3]=5"
        D2["DQ: [0,2]"]
        POPF["pop front: idx 0 ngoài cửa sổ"]
        D3["DQ: [2]"]
        POPB["pop back: A[2]=2 ≤ 5, rồi (empty)"]
        D4["DQ: [3]"]
        MAX2["max = A[3] = 5"]
        D2 --> POPF --> D3 --> POPB --> D4 --> MAX2
    end

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

Two-pointer dùng hai biến l (trái) và r (phải) cùng quét từ trái sang phải. Mở rộng r để tìm trạng thái hợp lệ; thu hẹp l khi vi phạm điều kiện.

3.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)

O(n) vì r chỉ tăng, l chỉ tăng — mỗi cái tăng tối đa n lần.

3.2 Bài toán: substring dài nhất không lặp ký tự

Dùng thêm HashMap để theo dõi lần xuất hiện gần nhất của mỗi ký tự:

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").

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

Đếm số phần tử distinct 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)

5. 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]".

6. 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 — Two-pointer áp dụng khi điều kiện 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 monotone: cửa sổ lớn hơn luôn vi phạm hoặc luôn hợp lệ hơn).

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.

7. 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 — kết hợp sliding window + CMS ra pattern "cửa sổ thời gian + frequency sketch": dùng 2 CMS luân phiên (swap mỗi nửa window) để rate limiting theo thời gian. Hiểu cả hai kỹ thuật mới triển khai được pattern này.
• HyperLogLog: tương tự, kết hợp HLL + sliding window cho "distinct count trong 5 phút gần nhất" — pattern phổ biến trong analytics dashboard.
• Mini-challenge top-K: bài thực hành — kết hợp monotonic deque hoặc heap + cửa sổ trượt để tìm top-K phần tử trên 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 freq > 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