Sliding Window 滑動視窗 ·

介紹
#

滑動視窗處理的是「連續子陣列 / 子字串」的問題。暴力枚舉所有區間是 O(n^2)，滑動視窗讓左右邊界都只往右走，每個元素只進出視窗各一次，降到 O(n)。

關鍵是視窗移動時，只更新進來和出去的那一個元素，不要重算整個視窗。

形式	視窗怎麼動	例子
固定長度	右邊進一個、左邊出一個	長度 `k` 的最大和、每個視窗的統計
可變長度，求最長	右邊一直擴，不合法時左邊縮到合法	最多 `k` 個 0 的最長子陣列
可變長度，求最短	右邊一直擴，合法時左邊盡量縮	和至少 `k` 的最短子陣列
數子陣列個數	以 `right` 結尾的合法子陣列有 `right - left + 1` 個	「剛好 K」用「最多 K」相減
視窗內的最大 / 最小值	單調佇列	滑動視窗最大值

能用可變長度視窗的前提是單調性：視窗變大時條件只會越來越難（或越來越容易）滿足。如果陣列有負數、條件不單調，通常要改用前綴和 + 雜湊表。

模板一：固定長度視窗
#

window = 0
for right, x in enumerate(nums):
    window += x                          # 進來
    if right >= k:
        window -= nums[right - k]        # 出去
    if right >= k - 1:                   # 視窗滿了才更新答案
        res = max(res, window)

視窗裡要維護的東西不一定是總和：

雜湊表 / 計數陣列：視窗內有幾種數（LC 2841、2461），第 x 小的負數（LC 2653，值域小，用計數陣列）。
「刪掉一段」轉成「留下一段」：從兩端拿 k 張牌 = 中間留下長度 n - k 的連續一段，求最小和（LC 1423）；刪掉長度 k 的子字串 = 剩下的位移 = 總位移減視窗位移（LC 3694）。
環狀陣列：把陣列接兩次，或用 i % n（LC 2134、1888）。
滾動雜湊：視窗移動時，乘上 / 除以 power，只更新頭尾（LC 2156）。

模板二：可變長度，求最長
#

left = 0
for right, x in enumerate(nums):
    加入(x)
    while 視窗不合法():
        移除(nums[left])
        left += 1
    res = max(res, right - left + 1)     # 縮完之後一定合法

最多 1 個 0：刪掉一個元素後全是 1 的最長長度，就是「最多一個 0 的最長視窗」再減 1（LC 1493）。

模板三：可變長度，求最短
#

left = 0
for right, x in enumerate(nums):
    加入(x)
    while 視窗合法():
        res = min(res, right - left + 1) # 合法時更新，再試著縮
        移除(nums[left])
        left += 1

不同值的和至少 k（LC 3795）：同一個值在視窗裡出現多次只算一次。記錄每個值最後一次出現的位置，左邊界移出時，只有它是最後一次出現才扣掉。

模板四：數子陣列個數
#

以 right 結尾、左端在 [left, right] 的子陣列都合法，共 right - left + 1 個：

def at_most(k):
    left = count = 0
    for right, x in enumerate(nums):
        加入(x)
        while 超過(k):
            移除(nums[left])
            left += 1
        count += right - left + 1
    return count

return at_most(k) - at_most(k - 1)       # 剛好 k

「剛好 K」不單調，但「最多 K」單調，所以用兩次「最多」相減（LC 1248）。如果條件是「花費 <= k」本身就單調，直接數就好（LC 3835）。

「至少 K」的寫法：視窗合法時就一直縮左邊，縮到剛好不合法為止。這時左端放在 [0, left) 的任何位置都合法，所以 count += left：

left = count = 0
for right, x in enumerate(nums):
    加入(x)
    while 視窗合法():
        移除(nums[left])
        left += 1
    count += left                        # 左端在 [0, left) 都合法

（LC 2962、1358、3325、3298、2537）。「剛好 K」也可以寫成「至少 K」減「至少 K + 1」（LC 3306）。

模板五：單調佇列維護視窗最值
#

from collections import deque

max_q = deque()                          # 存 index，值遞減
for right, x in enumerate(nums):
    while max_q and nums[max_q[-1]] <= x:
        max_q.pop()                      # 被 x 支配，之後不可能是最大值
    max_q.append(right)
    left = right - k + 1                 # 固定長度 k；可變長度時 left 由條件決定
    if max_q[0] < left:
        max_q.popleft()                  # 過期：已經在視窗外
    if left >= 0:
        res.append(nums[max_q[0]])       # 視窗最大值