[algorithms] Sliding Window 滑動視窗

視覺化概覽

flowchart TD
    A["初始化 left=0, right=0"] --> B["擴展視窗：right 右移"]
    B --> C{"滿足收縮條件？"}
    C -- 否 --> D["更新答案"]
    D --> E{"right < n？"}
    E -- 是 --> B
    E -- 否 --> F["結束"]
    C -- 是 --> G["收縮視窗：left 右移"]
    G --> H["移除 nums[left]"]
    H --> C

什麼是滑動視窗？

維護一個動態的子陣列/子字串區間。

陣列: [1, 3, 2, 6, -1, 4, 1, 8, 2]
視窗大小 k=5

[1, 3, 2, 6, -1] 4, 1, 8, 2  → 和=11
 1 [3, 2, 6, -1, 4] 1, 8, 2  → 和=14
 1, 3 [2, 6, -1, 4, 1] 8, 2  → 和=12
...

每次滑動：加入新元素，移除舊元素

兩種類型

1. 固定大小視窗

// 大小為 k 的視窗
int windowSum = 0;
for (int i = 0; i < k; i++) windowSum += nums[i];
 
for (int i = k; i < n; i++) {
    windowSum += nums[i] - nums[i-k];  // 進一出一
    // 處理結果
}

2. 可變大小視窗

int left = 0;
for (int right = 0; right < n; right++) {
    // 擴展視窗
    add(nums[right]);
 
    // 收縮視窗
    while (需要收縮) {
        remove(nums[left]);
        left++;
    }
 
    // 更新答案
    updateResult();
}

經典問題

1. 和 ≥ target 的最短子陣列

int minLen = Integer.MAX_VALUE;
int sum = 0, left = 0;
 
for (int right = 0; right < n; right++) {
    sum += nums[right];
 
    while (sum >= target) {
        minLen = Math.min(minLen, right - left + 1);
        sum -= nums[left++];
    }
}

2. 無重複字元的最長子串

Map<Character, Integer> lastIndex = new HashMap<>();
int left = 0, maxLen = 0;
 
for (int right = 0; right < n; right++) {
    char c = s.charAt(right);
 
    if (lastIndex.containsKey(c) && lastIndex.get(c) >= left) {
        left = lastIndex.get(c) + 1;
    }
 
    lastIndex.put(c, right);
    maxLen = Math.max(maxLen, right - left + 1);
}

3. 最小覆蓋子串

在 s 中找包含 t 所有字元的最短子串。

// need: t 中每個字元的需求
// window: 當前視窗中的字元計數
// valid: 滿足需求的字元數
 
while (right < n) {
    // 擴展
    if (need.contains(c)) {
        window[c]++;
        if (window[c] == need[c]) valid++;
    }
 
    // 收縮
    while (valid == need.size()) {
        更新最小長度;
        左邊界字元處理;
    }
}

4. 滑動視窗最大值

使用單調雙端隊列：

Deque<Integer> deque = new ArrayDeque<>();  // 存索引
 
for (int i = 0; i < n; i++) {
    // 移除超出視窗的
    while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
        deque.pollFirst();
    }
 
    // 保持遞減：移除比當前小的
    while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
        deque.pollLast();
    }
 
    deque.offerLast(i);
 
    if (i >= k - 1) {
        result[i-k+1] = nums[deque.peekFirst()];
    }
}

通用模板

int left = 0;
// 視窗狀態（Map、計數器、和等）
 
for (int right = 0; right < n; right++) {
    // 1. 擴展視窗：處理 nums[right]
 
    // 2. 收縮視窗（可變大小）
    while (需要收縮) {
        // 處理 nums[left]
        left++;
    }
 
    // 3. 更新答案
}

何時使用滑動視窗？

• 連續子陣列/子字串問題
• 需要找最長/最短滿足條件的區間
• 可以用增量方式維護狀態

時間複雜度

通常 O(n)：每個元素最多進出視窗一次

經典題目

題目	類型
長度為 k 的最大和	固定視窗
最小子陣列和 ≥ target	可變視窗
無重複最長子串	可變視窗
最小覆蓋子串	可變視窗
字串排列	固定視窗
滑動視窗最大值	固定+單調隊列

LeetCode 題號

1. 長度最小子陣列 - LeetCode 209
2. 無重複最長子串 - LeetCode 3
3. 最小覆蓋子串 - LeetCode 76
4. 字串排列 - LeetCode 567
5. 滑動視窗最大值 - LeetCode 239
6. K 個不同字元 - LeetCode 340

相關檔案

• Java 實作：SlidingWindow.java