一個會伸縮的窗框掃過資料,求連續一段的最佳解。O(n²) 變 O(n)。
固定大小(fixed) —— 窗寬固定 k,一路右滑。每滑一格:加進來一個、丟掉一個,和 / 平均 O(1) 更新。例:k 個連續數的最大和、移動平均。
可變大小(variable) —— 右指標擴張納入新元素;一旦違反條件(太多、超過上限),左指標收縮。例:最長不重複子字串、和 ≥ target 的最短子陣列。
核心心法 —— 不要每次重算整個視窗,用「加右、減左」增量更新,才省下那個 n。
為什麼是 O(n) —— 每個元素最多進出視窗各一次,合起來 O(n)。
暴力法 —— 列出所有連續區間有 O(n²) 個,每個還要算和,更慢。
滑動視窗 —— 利用「連續」的特性:右移一格,只變動兩個元素(進一個、出一個)。
固定窗 —— 每步 O(1) 更新、共 n 步 → O(n)。
可變窗 —— 左右指標都只往右走、各最多 n 步 → O(n)。
O(1) 更新要維護的量(和、字元計數…)?兩個都 yes 就適合。車往前開,窗景一格格換:進來新的、離開舊的,不用重看整條街。
一個框框在文字上滑,每次只看框內那幾個字。
每天更新「最近 7 天」:加上今天、丟掉 8 天前那天。
視窗寬 k=3,在 [2, 1, 5, 1, 3, 2] 上一路右滑,求「3 個連續數的最大和」。紫色是視窗內、淡掉的是已滑過。每滑一格只要減掉離開的、加上進來的(O(1) 更新),不用重算整個視窗。按「下一步」。
從固定視窗最大和、移動平均,到最長不重複子字串、最短子陣列、異位詞、最小覆蓋子字串、單調 deque。
❌ 每次重算整個視窗 —— 那就退回 O(n·k),失去意義。要「加右、減左」增量更新。
❌ 可變窗收縮條件寫錯 —— while 要收縮到「剛好合法」為止,邊界(> vs >=)想清楚。
❌ 忘了更新答案的時機 —— 固定窗滿 k 才算一個完整視窗;可變窗要在「合法」時更新。
❌ 用在不連續的問題 —— 滑動視窗只適合「連續子陣列 / 子字串」,不連續的子序列不行(那多半是 DP)。
[2,1,5,1,3,2] 視窗 k=3,每個視窗的和各是多少?最大和落在哪個視窗?O(1),不用重新加總整個視窗?O(n) 而不是 O(n²)?把答案打到對話裡,我幫你對。