Sliding Window Pattern: Tối ưu xử lý mảng và chuỗi từ O(N²) xuống O(N)
Hướng dẫn Sliding Window Pattern từ O(N²) xuống O(N): fixed window, two pointers, longest substring, minimum subarray, monotonic deque và TypeScript.
ShanverseCập nhật 10 phút đọc— lượt xemĐang tải lượt xem
Performance
Data Structures
Bài toán cốt lõi
Giả sử cần tìm tổng lớn nhất của mọi subarray dài k.
Cách brute force:
Có N-K+1 cửa sổ, mỗi cửa sổ cộng lại K phần tử: O(NK), và trở thành O(N²) khi
Bình luận
K
tỷ lệ với
N
.
Nhưng hai cửa sổ kế tiếp chỉ khác hai phần tử:
Đó là nền tảng của Sliding Window.
Khi nào nhận ra Sliding Window?
Thường phù hợp khi đề bài có:
Đoạn liên tục: subarray, substring hoặc chuỗi sự kiện liên tiếp.
Từ khóa: longest, shortest, maximum, minimum, at most, exactly.
Có thể cập nhật trạng thái khi thêm/bớt một phần tử.
Hai biên left và right chỉ tiến về phía trước.
Điều kiện cửa sổ có tính chất đủ “monotonic” để biết lúc nào mở rộng hoặc thu hẹp.
Không phù hợp chỉ vì đề bài có array. Subsequence không liên tục, pair tùy ý, negative numbers hoặc điều kiện không monotonic có thể cần prefix sum, hash map, dynamic programming hay cấu trúc dữ liệu khác.
Hai loại cửa sổ
Fixed-size Sliding Window
Mỗi phần tử được thêm một lần và loại một lần: thời gian O(N), bộ nhớ phụ O(1).
Template fixed window
Ý tưởng quan trọng không phải copy slice(), mà là giữ incremental state như sum, frequency map hoặc deque.
Variable-size Sliding Window
Cửa sổ [left, right] có kích thước:
Template cho bài toán “longest valid window”:
Invariant sau vòng while: cửa sổ hiện tại luôn hợp lệ. Với bài toán minimum valid window, thường phải cập nhật đáp án bên trongwhile (windowIsValid()) trước khi thu hẹp.
Ví dụ 1: Longest Substring Without Repeating Characters
Dùng frequency map
Thời gian O(N), bộ nhớ O(U) với U là số ký tự khác nhau trong cửa sổ.
Nhảy trực tiếp left
Điều kiện previous >= left rất quan trọng; nếu thiếu, left có thể đi lùi.
Unicode trong JavaScript
text[index] xử lý UTF-16 code unit, có thể tách emoji thành hai phần. Array.from(text) xử lý Unicode code point tốt hơn, nhưng vẫn không đồng nghĩa với grapheme mà người dùng nhìn thấy. Với emoji ghép, dấu kết hợp hoặc cờ quốc gia, dùng Intl.Segmenter nếu bài toán cần ký tự trực quan.
Ví dụ 2: Minimum Size Subarray Sum
Tìm đoạn ngắn nhất có tổng >= target khi mọi phần tử đều không âm.
Tại sao cần số không âm? Khi mở rộng, tổng không giảm; khi thu hẹp, tổng không tăng. Nếu có số âm, tính monotonic bị phá vỡ và Sliding Window này có thể bỏ lỡ đáp án.
Với số âm, bài “shortest subarray sum at least K” thường dùng prefix sum + monotonic deque, không dùng template trên.
Ví dụ 3: Longest Ones sau tối đa k lần flip
Invariant: cửa sổ luôn chứa nhiều nhất k số 0.
Ví dụ 4: At Most K Distinct
Với bài đếm subarray có chính xác k phần tử khác nhau:
Công thức áp dụng cho hàm đếm cửa sổ, không phải lấy hai giá trị “longest” trừ nhau.
Maximum trong mỗi cửa sổ: cần Monotonic Deque
Nếu mỗi lần gọi Math.max(...window) thì vẫn là O(NK). Dùng deque chứa index, giá trị giảm dần:
Mỗi index được push và pop tối đa một lần, nên O(N) amortized; bộ nhớ O(K).
Tránh Array.shift() trong hot loop vì việc dời phần tử có thể tốn O(K).
Vì sao Variable Window là O(N), không phải O(N²)?
Có vòng while bên trong for, nhưng:
right tăng tối đa N lần.
left cũng chỉ tăng, tối đa N lần.
Mỗi phần tử vào và rời cửa sổ tối đa một lần.
Tổng số lần dịch chuyển là ≤ 2N, nên O(N) nếu add, remove và kiểm tra điều kiện là O(1) amortized.
Nếu mỗi bước copy cả cửa sổ, sort lại, hoặc scan lại toàn bộ map thì không còn O(N).
Sliding Window và Two Pointers
Sliding Window là một dạng Two Pointers nhưng nhấn mạnh một đoạn liên tục và trạng thái của đoạn đó.
Sliding Window:[left, right] mô tả subarray/substring liên tục.
Opposite-direction pointers: hai đầu của sorted array để tìm pair.
Fast/slow pointers: cycle detection hoặc compact array.
Không nên ép mọi bài Two Pointers vào template cửa sổ.
Những trường hợp dễ dùng sai
1. Có số âm
Variable window dựa trên tổng thường sai vì mở rộng có thể làm tổng giảm. Cân nhắc:
Prefix sum + hash map cho exact sum.
Prefix sum + monotonic deque cho shortest sum >= K.
2. Không liên tục
Subsequence không phải subarray. Sliding Window chỉ xử lý một đoạn liên tiếp.
3. Điều kiện không monotonic
Nếu không biết việc tăng right hoặc left ảnh hưởng tính hợp lệ theo hướng nào, một cửa sổ duy nhất có thể không đủ.
4. State update không O(1)
Median mỗi cửa sổ không thể cập nhật bằng một biến sum. Cần two heaps, multiset hoặc balanced tree, thường O(N log K).
5. Overflow và precision
JavaScript number chỉ biểu diễn integer chính xác đến Number.MAX_SAFE_INTEGER. Tổng/count rất lớn cần kiểm tra constraint hoặc dùng bigint đồng nhất.
Off-by-one checklist
Chọn rõ interval [left, right] hay [left, right).
Với interval inclusive, length là right - left + 1.
Fixed window bắt đầu trả kết quả khi right >= k - 1.
Validate k = 0, k > N, array rỗng.
Với min window, cập nhật đáp án trước khi shrink làm cửa sổ invalid.
Khi frequency về 0, xóa key khỏi map nếu dùng map.size.
Không cho left đi lùi khi dùng last-seen index.
Streaming và time-based windows
Cửa sổ không chỉ dành cho array có sẵn. Với event stream:
Code này giả định event đến theo thứ tự timestamp. Out-of-order events, late arrival và distributed stream cần watermark/window semantics rõ hơn.
Cách giải một bài Sliding Window
Xác nhận kết quả là đoạn liên tục.
Chọn fixed hay variable window.
Định nghĩa invariant của cửa sổ.
Xác định state cần giữ: sum, count, frequency map hay deque.
Viết thao tác add và remove.
Quyết định khi nào cập nhật đáp án.
Chứng minh hai pointer chỉ tiến về trước.
Kiểm tra điều kiện monotonic, đặc biệt với negative numbers.
Test empty input, k=1, k=N, duplicates và Unicode.
Đo thực tế; đừng gọi là O(N) nếu vẫn copy/sort/scan cửa sổ.
Bài tập gợi ý
Maximum Average Subarray I.
Longest Substring Without Repeating Characters.
Minimum Size Subarray Sum.
Max Consecutive Ones III.
Fruit Into Baskets.
Permutation in String.
Minimum Window Substring.
Sliding Window Maximum.
Subarrays with K Different Integers.
Kết luận
Sliding Window giảm công việc lặp lại bằng cách duy trì incremental state cho đoạn [left, right]:
Độ phức tạp O(N) đến từ việc mỗi pointer chỉ tiến về trước, không phải chỉ vì có hai biến left/right. Hãy kiểm tra tính liên tục, invariant, monotonicity và chi phí cập nhật state. Nếu negative numbers hoặc aggregate phức tạp phá vỡ những điều kiện đó, prefix sum, monotonic deque, heap hay thuật toán khác mới là lựa chọn đúng.
Mục lục(27)
Codetypescript
1functionmaxSumBruteForce(numbers:number[], k:number):number {2if (k <=0|| k > numbers.length) {3thrownewRangeError("Invalid window size");4 }56let best =-Infinity;78for (let start =0; start <= numbers.length- k; start++) {9let sum =0;10for (let index = start; index < start + k; index++) {11 sum += numbers[index];12 }13 best = Math.max(best, sum);14 }1516return best;17}
Codeplain text
1[2, 1, 5] + 1 mới - 2 cũ → [1, 5, 1]
Codeplain text
1right - left + 1
Codeplain text
1exactly(k) = atMost(k) - atMost(k - 1)
Codeplain text
1Expand right → update state → shrink left when needed → update answer
Hướng dẫn dùng Bitwise Operations và Bitmask cho Permissions/RBAC: TypeScript Number/BigInt, database BIGINT, middleware, migration, indexing và giới hạn bảo mật.
Hướng dẫn Fast & Slow Pointers và Floyd’s Cycle Detection bằng TypeScript: phát hiện cycle, tìm entry, cycle length, functional graph và các giới hạn thực tế.
