滑動視窗是指 在一個有序的資料結構(陣列、字串)上維護一個可動態收縮視窗。

當視窗滑動時，只更新更變動的部分，而不是全部更新，在藉由更新變動的部分來判斷視窗是否需要滑動或寬度是否減小。

序列:  [ a  b  c  d  e  f  g ]
         ↑              ↑
        left           right
         └──────────────┘
              視窗 (window)

→ right 右移：視窗擴張，納入新元素
→ left  右移：視窗收縮，移除舊元素

操作方式

1. 固定視窗

滑動視窗的寬度固定不變，且固定會向右滑動

def fix_window(nums, k):
    window_width = sum(nums[:k])
    result = window_width

    for right in range(k, len(nums)):
        window_width += nums[right]
        window_width -= nums[right - k]
        result = max(result, window_width)

    return result

nums[:k]切片語法講解

從索引 0 開始，取到索引 k 之前（不包含 k）的所有元素

nums = [1, 3, 2, 5, 4],  k = 3

迴圈前:
[1  3  2] 5  4 
window_width = sum(nums[:3]) = sum(1,3,2) = 6

初始迴圈:
right == 3
window_width = 6 + nums[3] = 6 + 5  == 11
window_width = 11 - nums[3-3] = 11 - 1 == 10
[1  3  2] 5  4  變成  1 [3  2  5] 4   

第二回圈:
right == 4
window_width = 10 + nums[4] = 10 + 4 == 14
window_width = 14 - nums[1] = 14 - 3 == 11
1 [3  2  5] 4  變成 1  3 [2  5  4]

2. 動態變化視窗

滑動視窗的寬度會根據條件而增加或減少

def dynamic_window(s):
    left = 0
    result = 0
    window_state = {}  # 記錄視窗內的狀態

    for right in range(len(s)):
        # Step 1: 將 s[right] 加入視窗
        window_state[s[right]] = ...

        # Step 2: 視窗不合法時，縮小左邊
        while 視窗不符合條件:
            window_state[s[left]] = ...
            left += 1

        # Step 3: 更新答案
        result = max(result, right - left + 1)

    return result

使用時機

當情況同時符合下述特徵時使用

1. input為有序序列，如array、string
2. output要求是連續的array/string 或 找最大、最小、剛好等極的值
3. 需滿足 不重複、總和≤k、最多k個不同字元 等條件

實際應用

1. 網路流量監控:每秒偵測過去 60 秒內的請求總數，超過閾值就觸發警報 所以視窗寬度固定為60秒
2. 串流平台緩衝區管理:預先載入N秒內的影片資料 所以每過N秒視窗會向右滑動N秒的距離
3. 金融異常偵測:偵測某支股票在任意連續 7 天內的漲跌幅度是否超過20%