[algorithms] Sliding Window 滑動視窗

滑動視窗是雙指標的特化版。right 負責擴展、left 負責收縮，每個元素最多進出各一次，所以是 O(n)。學會這個模板，一大堆「最長/最短子陣列/子字串」的題目都能秒殺。

先講結論

滑動視窗分兩種：固定大小（easy）和可變大小（medium/hard）。可變大小的通用模板長這樣：右邊擴展 → 判斷是否需要收縮 → 更新答案。背好這個骨架，細節再按題目調整。

固定大小視窗

求大小為 k 的子陣列最大和：

int windowSum = 0;
for (int i = 0; i < k; i++) windowSum += nums[i];
int maxSum = windowSum;
 
for (int i = k; i < n; i++) {
    windowSum += nums[i] - nums[i-k];  // 進一個、出一個
    maxSum = Math.max(maxSum, windowSum);
}

核心思想：視窗滑動時不要重算整個區間，只更新「進來的」和「出去的」。

可變大小視窗：通用模板

int left = 0;
// 視窗狀態（Map、計數器、和...）
 
for (int right = 0; right < n; right++) {
    // 1. 擴展：把 nums[right] 加入視窗
 
    // 2. 收縮：不滿足條件時 left 右移
    while (需要收縮) {
        // 把 nums[left] 移出視窗
        left++;
    }
 
    // 3. 更新答案
}

每個元素最多被 left 和 right 各訪問一次 → O(n)。

經典問題

1. 和 >= target 的最短子陣列

int minLen = Integer.MAX_VALUE, 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++];
    }
}

注意：這裡是「滿足條件時收縮」（找最短），跟「不滿足條件時收縮」（找最長）的方向相反。搞混這個是滑動視窗最常見的 bug。

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);
}

LeetCode 3，面試超高頻。

3. 最小覆蓋子串

在 s 中找包含 t 所有字元的最短子串。這是滑動視窗的 hard 題代表。

思路：用一個 Map 記錄 t 中每個字元的需求，視窗擴展時更新 window map，全部滿足時開始收縮找最短。

// 精簡版邏輯
while (right < n) {
    // 擴展：把 s[right] 加入 window
    if (need.containsKey(c)) {
        window.merge(c, 1, Integer::sum);
        if (window.get(c).equals(need.get(c))) valid++;
    }
 
    // 收縮：全部滿足時找最短
    while (valid == need.size()) {
        更新最小長度;
        移除左邊界字元;
    }
}

4. 滑動視窗最大值

固定大小視窗，但要維護最大值。暴力每次找最大要 O(k)，用單調雙端隊列降到 O(1)：

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()];
}

這題同時用到滑動視窗和單調棧的概念。

什麼時候用滑動視窗？

三個條件同時成立：

1. 求的是連續子陣列/子字串
2. 需要找最長/最短滿足某條件的區間
3. 可以用增量方式維護狀態（加一個元素、減一個元素）

如果不是連續的（比如子序列），那就不是滑動視窗的場景，可能要用 DP。

---

滑動視窗就像坐火車看風景：你的視野（視窗）隨著火車（right）前進，但太遠的風景（left 之前的元素）就看不到了。差別是你可以控制視窗大小。