滑動視窗 (Sliding Window)#

滑動視窗（Sliding Window）是 雙指標 的一個特例：兩根指標 left 與 right 都從左端出發、只往右走，中間框住的那一段就是「視窗」。它專門對付「連續子陣列／子字串」的問題，把暴力枚舉所有子區間的 O(n²) 降到 O(n)。

為什麼可行#

暴力解枚舉所有連續子區間需要兩層迴圈：外層定左端、內層定右端，共 O(n²) 個區間，每個再花 O(n) 計算的話甚至到 O(n³)。

滑動視窗能更快的關鍵在於：右端右移時，新視窗的資訊可以從舊視窗增量得到，不必重算整段。例如視窗和只要加上新進來的元素、減去滑出去的元素；視窗內字元頻率只要對新舊兩個字元各做一次增減。因為 left 與 right 全程都只增不減，兩者各自最多走 n 步，總共 O(n)。

滑動視窗成立有一個前提：問題必須具有單調性——當視窗變大時某個性質單調惡化、變小時單調改善（例如「和」隨長度單增、「是否含重複字元」隨擴張只會更糟）。有了單調性，left 才能放心地只往右收縮而不回頭。

觸發訊號#

看到下面這些特徵，優先想滑動視窗：

  • 求的是連續子陣列／子字串（不是子序列）。
  • 目標是這段連續結構的最長／最短／計數／是否存在。
  • 暴力解就是兩層迴圈枚舉所有 [left, right] 區間，O(n²)。
  • 視窗的某個統計量（和、頻率表、distinct 個數）可以增量維護。

「子陣列／子字串」幾乎等同「連續」，要往滑動視窗或 雙指標 想；「子序列」可以不連續，通常是 動態規劃 的地盤。一字之差，解法天差地別。

固定長度視窗#

視窗長度固定為 k。right 每步前進並把新元素納入統計；當視窗長度達到 k，就處理一次當前視窗，然後 left++ 讓視窗整體右移。

模板：

var left = 0
for (right in 0 until n) {
    // 1. 把 nums[right] 納入視窗統計
    add(nums[right])

    // 2. 視窗還沒滿 k，繼續擴張
    if (right - left + 1 < k) continue

    // 3. 視窗剛好為 k：在此更新答案
    updateAnswer()

    // 4. 移出最左元素，左界右移，維持長度 k
    remove(nums[left])
    left++
}

代表題一：長度為 k 的最大子陣列和。 維護一個視窗和，進一個減一個即可。

代表題二：找字串中所有變位詞（anagram）的起始位置 ↗。 視窗長度固定為 pattern 長度，視窗內維護一張字元頻率表，與 pattern 的頻率表相等時即為一個變位詞。

// 在 s 中找出所有 p 的變位詞起始下標
fun findAnagrams(s: String, p: String): List<Int> {
    val res = mutableListOf<Int>()
    if (s.length < p.length) return res

    val need = IntArray(26)
    val window = IntArray(26)
    for (c in p) need[c - 'a']++

    val k = p.length
    var left = 0
    for (right in s.indices) {
        window[s[right] - 'a']++                 // 納入新字元

        if (right - left + 1 < k) continue        // 視窗未滿

        if (window.contentEquals(need)) {         // 頻率表相等即變位詞
            res.add(left)
        }

        window[s[left] - 'a']--                    // 移出最左字元
        left++
    }
    return res
}

固定窗的判斷標準很單純：題目直接或間接給定了視窗長度（「長度為 k」「等於 pattern 長度」）。left 與 right 像綁在一起的尺，整把往右滑。

動態長度視窗#

視窗長度不固定。right 持續擴張；一旦視窗違反了題目的約束，就用 while 不斷 left++ 收縮直到重新合法；視窗合法時更新答案。

模板：

var left = 0
for (right in 0 until n) {
    add(nums[right])                  // 擴張：右界納入新元素

    while (windowIsInvalid()) {       // 收縮：違反約束就移出左端
        remove(nums[left])
        left++
    }

    updateAnswer()                    // 此刻視窗合法，更新答案
}

代表題一：無重複字元的最長子字串 ↗。 約束是「視窗內不能有重複字元」，一旦出現重複就從左收縮到不重複為止。

fun lengthOfLongestSubstring(s: String): Int {
    val count = HashMap<Char, Int>()
    var left = 0
    var best = 0

    for (right in s.indices) {
        val c = s[right]
        count[c] = count.getOrDefault(c, 0) + 1        // 擴張

        while (count[c]!! > 1) {                         // 出現重複，收縮
            val d = s[left]
            count[d] = count[d]!! - 1
            left++
        }

        best = maxOf(best, right - left + 1)            // 視窗合法，更新答案
    }
    return best
}

代表題二：最小覆蓋子字串（minimum window substring） ↗。 在 s 中找最短的子字串，使其涵蓋 t 的所有字元（含重複次數）。這裡的「合法」是「已覆蓋全部所需字元」，因此是 while (合法) { 嘗試縮短並更新答案; left++ }，與上題收縮方向相反，正好示範動態窗收縮條件的彈性。

fun minWindow(s: String, t: String): String {
    val need = IntArray(128)
    var required = t.length
    for (c in t) need[c.code]++

    var left = 0
    var bestLen = Int.MAX_VALUE
    var bestStart = 0
    for (right in s.indices) {
        if (need[s[right].code] > 0) {                  // 補上一個需要的字元
            required--
        }
        need[s[right].code]--

        while (required == 0) {                          // 已覆蓋：盡量縮短
            if (right - left + 1 < bestLen) {
                bestLen = right - left + 1
                bestStart = left
            }
            need[s[left].code]++
            if (need[s[left].code] == 1) {               // 移出後若造成缺口，停止收縮
                required++
            }
            left++
        }
    }

    return if (bestLen == Int.MAX_VALUE) "" else s.substring(bestStart, bestStart + bestLen)
}

動態窗的精髓是**「右擴左縮」的不變式**：right 負責探索更多可能，left 負責把不合法的部分擠掉。寫對的關鍵是想清楚兩件事——「什麼條件下視窗不合法（要收縮）？」與「答案該在擴張後還是收縮後更新？」。

進階：視窗極值與單調佇列#

如果題目要的不是視窗的「和／計數」，而是**滑動視窗最大值（Sliding Window Maximum） ↗**——隨著視窗滑動，回報每個視窗內的最大元素——單純的增量維護就不夠了，因為被移出的若恰好是最大值，得重新找次大值。

解法是搭配一個單調遞減的雙端佇列（deque）：佇列裡只保留「可能成為未來最大值」的候選下標，並維持對應值由大到小。新元素進來時，從佇尾彈掉所有比它小的（它們永遠不可能再當最大值），佇首永遠是當前視窗最大值；佇首下標滑出視窗時從佇首彈出。每個元素至多進出佇列一次，整體仍是 O(n)。

「維護視窗極值」是單調資料結構的經典應用。單調堆疊／單調佇列的原理與更多題型，見 單調佇列；字串相關的進階匹配（如 KMP）則見 字串匹配。

為什麼單調 deque 能 O(n) 求視窗最大值

關鍵觀察：當一個較小的元素 a 進入視窗後，又來了一個更大且更靠右的元素 b，那麼只要 b 還在視窗內，a 就永遠不可能成為任何視窗的最大值（任何包含 a 的視窗也必包含更大的 b）。所以 a 可以被安全丟棄。

deque 因此維持「下標對應的值嚴格遞減」：

  • 入隊（右擴）：把佇尾所有 ≤ 新元素的下標彈掉，再把新下標放入佇尾。
  • 出窗（左縮）：若佇首下標 < right - k + 1（已離開視窗），從佇首彈出。
  • 取答：佇首下標對應的值就是當前視窗最大值。

每個下標恰好入隊一次、出隊一次，攤還 O(1)，全程 O(n)。求視窗最小值只要把比較方向反過來，維持遞增即可。

小結#

固定窗與動態窗共用「left/right 單向滑動」的骨架，差別只在視窗長度是否由題目固定，以及收縮的時機：

比較項固定長度視窗動態長度視窗
視窗長度題目給定為 k隨約束變化
left 移動時機每當長度達 k，固定 left++while 違反約束時持續 left++
left/right 關係同步前進，間距恆為 k各自獨立，間距浮動
更新答案時機視窗滿 k 時視窗合法時（擴張後或收縮中）
代表題長度 k 最大子陣列和、找變位詞無重複字元最長子字串、最小覆蓋子字串
求視窗極值搭配 單調佇列 deque同左

拿到題目先判一件事：視窗該不該定長？ 定長就套固定窗的 if 滿了就右移；不定長就套動態窗的 while 違反就收縮。其餘的差異，都是在這兩個模板上換掉「視窗統計量」與「合法條件」而已。

Backward 雙指標 前綴和 Forward