Cấu trúc dữ liệu và Giải thuật Bài 23: Cửa sổ trượt kích thước linh hoạt (Variable Sliding Window).

Cửa sổ trượt kích thước cố định mang lại sự ổn định tuyệt đối nhờ một chiếc khung không bao giờ biến dạng. Nhưng trong thực tế nghiệp vụ, dữ liệu hiếm khi ngoan ngoãn chui tọt vào một con số $K$ định sẵn. Thay vì tìm "tổng của đúng 3 ngày", yêu cầu hệ thống thường là: "Tìm giai đoạn ngắn nhất đạt doanh thu 100 triệu", hoặc "Tìm chuỗi hành động dài nhất của user mà không lặp lại thao tác nào".

Lúc này, chiếc khung cứng nhắc phải biến thành một sợi dây thun co giãn. Kỹ thuật Cửa sổ trượt linh hoạt (Variable Sliding Window) chính là nghệ thuật điều khiển sợi dây thun đó: phình to ra để đáp ứng điều kiện, và thu nhỏ lại để tối ưu hóa kết quả.

1. Mô hình "Con sâu đo" trong bộ nhớ

Cách hoạt động của Cửa sổ trượt linh hoạt rất giống với cách một con sâu đo di chuyển trên cành cây, sử dụng hai con trỏ left và right:

1. Phình to (Expand): Con trỏ right không ngừng tiến về phía trước để thu thập thêm dữ liệu vào cửa sổ. Nó chỉ dừng lại khi dữ liệu bên trong cửa sổ đã thỏa mãn điều kiện của bài toán (hoặc khi đụng phải phần tử vi phạm luật).

2. Thu nhỏ (Shrink): Ngay khi điều kiện được thỏa mãn (hoặc bị vi phạm), con trỏ left bắt đầu bò theo để thu hẹp cửa sổ lại. Mục đích của việc thu hẹp là vứt bỏ những phần tử thừa thãi ở mép trái nhằm tìm ra kích thước tối ưu nhất (ngắn nhất/dài nhất), cho đến khi cửa sổ không còn hợp lệ nữa.

3. Lặp lại quá trình trên cho đến khi right đi hết mảng.

2. Bài toán Tối ưu Min: Mảng con ngắn nhất có tổng $\ge S$

Đây là bài toán kinh điển đo lường khả năng phản xạ với Sliding Window.

Yêu cầu: Cho mảng số nguyên dương và một số mục tiêu $S$. Hãy tìm độ dài của mảng con liên tiếp ngắn nhất có tổng lớn hơn hoặc bằng $S$. Nếu không có, trả về 0.

Ví dụ: Mảng [2, 3, 1, 2, 4, 3], mục tiêu $S = 7$.

Thay vì thử mọi mảng con $O(n^2)$, chúng ta điều khiển "con sâu đo":

• right kéo dài cửa sổ: [2, 3, 1, 2] (Tổng = 8 $\ge$ 7). Điều kiện đã thỏa mãn! Độ dài hiện tại là 4.

• left bắt đầu thu hẹp để tối ưu: Bỏ số 2 ở đầu $\rightarrow$ [3, 1, 2] (Tổng = 6). Hết thỏa mãn. Quá trình thu hẹp dừng lại.

• right lại tiến lên: Thêm 4 $\rightarrow$ [3, 1, 2, 4] (Tổng = 10 $\ge$ 7). Độ dài là 4.

• left lại thu hẹp: Bỏ số 3 $\rightarrow$ [1, 2, 4] (Tổng = 7 $\ge$ 7). Thỏa mãn! Độ dài tối ưu mới là 3. Cứ tiếp tục như vậy.

Triển khai bằng Golang:

Dù nhìn có vẻ như có 2 vòng lặp lồng nhau (một for, một while), nhưng thực chất mỗi phần tử chỉ bị con trỏ right "nuốt" vào đúng 1 lần, và bị con trỏ left "nhả" ra đúng 1 lần. Tổng thời gian vẫn là $O(n)$.

Go

import "math"

func minSubArrayLen(target int, nums []int) int {
    n := len(nums)
    minLength := math.MaxInt32 // Đặt một kỷ lục vô cực để dễ dàng tìm giá trị nhỏ hơn
    currentSum := 0
    left := 0

    // Con trỏ right liên tục mở rộng cửa sổ
    for right := 0; right < n; right++ {
        currentSum += nums[right]

        // Ngay khi cửa sổ thỏa mãn điều kiện, kích hoạt vòng lặp Shrink (thu hẹp)
        for currentSum >= target {
            // 1. Cập nhật kỷ lục độ dài ngắn nhất
            windowSize := right - left + 1
            if windowSize < minLength {
                minLength = windowSize
            }
            
            // 2. Thu hẹp mép trái: trừ giá trị, nhích con trỏ left
            currentSum -= nums[left]
            left++
        }
    }

    if minLength == math.MaxInt32 {
        return 0
    }
    return minLength
}

3. Bài toán Tối ưu Max: Chuỗi con dài nhất không chứa ký tự lặp lại

Đây là bài toán LeetCode Medium (Bài 3) xuất hiện trong hầu hết các buổi phỏng vấn backend, đặc biệt khi xử lý log văn bản hoặc parsing chuỗi.

Yêu cầu: Cho một chuỗi ký tự, tìm độ dài của chuỗi con dài nhất không chứa bất kỳ ký tự nào bị lặp lại.

Ví dụ: Chuỗi "abcabcbb" $\rightarrow$ Kết quả là 3 (chuỗi "abc").

Logic của cửa sổ trượt lúc này thay đổi một chút:

• Chúng ta dùng thêm một Hash Map (Bảng băm) để ghi nhớ tần số của các ký tự đang nằm trong cửa sổ.

• right mở rộng cửa sổ và nhét ký tự vào Hash Map.

• Nếu phát hiện ký tự bị trùng (tần số $> 1$), cửa sổ đã vi phạm luật. Ngay lập tức, left phải di chuyển sang phải, vứt bỏ dần các ký tự cho đến khi ký tự trùng lặp bị tống khứ hoàn toàn khỏi cửa sổ.

Go

func lengthOfLongestSubstring(s string) int {
    charCount := make(map[byte]int) // Lưu tần số ký tự trong cửa sổ
    maxLength := 0
    left := 0

    for right := 0; right < len(s); right++ {
        charIn := s[right]
        charCount[charIn]++

        // Nếu phát hiện vi phạm (ký tự bị lặp lại)
        for charCount[charIn] > 1 {
            charOut := s[left]
            charCount[charOut]-- // Vứt bỏ ký tự mép trái
            left++               // Thu hẹp cửa sổ
        }

        // Lúc này cửa sổ chắc chắn hợp lệ, tiến hành cập nhật kỷ lục
        windowSize := right - left + 1
        if windowSize > maxLength {
            maxLength = windowSize
        }
    }

    return maxLength
}

4. Nhận diện "Mùi" của Variable Sliding Window

Khi thiết kế thuật toán cho các dự án thực tế, làm sao Hiếu biết bài toán này cần Cửa sổ trượt linh hoạt chứ không phải Hai con trỏ ngược chiều hay Prefix Sum? Hãy tìm 3 dấu hiệu sau:

1. Yêu cầu tính liên tục: Bài toán bắt buộc phải là "Mảng con" (Subarray) hoặc "Chuỗi con" (Substring), không được phép bốc các phần tử rời rạc.

2. Yêu cầu cực trị: Đề bài hỏi tìm "Dài nhất" (Longest) hoặc "Ngắn nhất" (Shortest).

3. Điều kiện tuyến tính (Monotonic): Khi bạn mở rộng cửa sổ, một giá trị (như tổng hoặc số lượng) liên tục tăng lên. Khi bạn thu hẹp, nó liên tục giảm xuống. Không có sự trồi sụt thất thường.

5. Ứng dụng ở tầng Kiến trúc hệ thống

Không chỉ là các vòng for và mảng số, tư duy này đang vận hành các hạ tầng mạng khổng lồ:

• TCP Dynamic Sliding Window: Giao thức TCP trên mạng Internet không gửi cố định $K$ gói tin. Nếu đường truyền tốt, nó mở rộng "cửa sổ" để gửi nhiều dữ liệu hơn cùng lúc (Expand). Nếu phát hiện rớt mạng (vi phạm điều kiện), nó lập tức thu nhỏ cửa sổ lại (Shrink) để tránh nghẽn mạng (Congestion Control).

• Log Parsing (Phân tích log): Khi đọc file log của hệ thống để tìm nguyên nhân crash, các công cụ giám sát sử dụng Sliding Window để trích xuất ra chuỗi hành động bất thường dài nhất của một user session trước khi hệ thống sập.

Đến đây, chúng ta đã khai thác triệt để các kỹ thuật duyệt mảng một chiều bằng sự dịch chuyển của các chỉ mục. Tuy nhiên, mảng không chỉ dùng để tìm kiếm. Đôi khi chúng ta cần sắp xếp lại một mảng hỗn độn thành các phân khu có tổ chức. Kỹ thuật tiếp theo sẽ đưa chúng ta trở về với một trong những bài toán thuật toán vĩ đại nhất thế kỷ 20 do Dijkstra sáng tạo ra.