滑动窗口 - YHT's Note Repo

%% # 纲要 > 主干纲要、Hint/线索/路标 # Q&A #### 已明确 #### 待明确 > 当下仍存有的疑惑 **❓ 有什么问题？** # Buffer ## 闪念 > sudden idea ## 候选资料 > Read it later %% # 滑动窗口滑动窗口 **==右边界==每次向右移动一步**，相当于在是 **==枚举/搜索==以==每个位置 `i` 作为右边界==的情况**，在每种情况下再去考虑**是否需要收缩左边界**。其要求保证 **==左边界==只可能==向右收缩==，而不会向左回头**，从而 **减少了搜索空间**。算法只遍历了数组两次，而**不用枚举所有可能的区间**，把 $O(n^2)$ 的时间复杂度降到了 $O(n)$。 --- 滑动窗口在实现上属于 "同向双指针" 的一种，强调 "窗口" 的概念，根据条件对窗口进行 "**右扩展、左收缩、滑动**"。由此确认**所有**符合条件的**连续区间段（每个区间都要是最大化的、不可再扩张的区间）** ## 滑动窗口适用的条件能够应用滑动窗口的**前提条件**如下： > [!summary] > 对于**任意两个分别以 `l1`、`l2` 为左边界的==满足目标条件的极大窗口== `[l1, r1]` 与 `[l2, r2]`**， > **如果当 `l1 < l2` 时，一定有 `r1 <= r2` 成立**，则**可应用滑动窗口方法**。 > 上述条件成立时，意味着**当滑窗==右边界==枚举到 `r2`** 时，**已然搜索完了 "以`l1` 为左端的所有窗口"**，故 **==可收缩左边界 `l1`==**，而不用再回头。 ![[Excalidraw-Solution/滑动窗口_0.excalidraw.svg|341]] %%[[Excalidraw-Solution/滑动窗口_0.excalidraw.md|🖋 Edit in Excalidraw]]%% # 变长的滑动窗口变长滑动窗口的思路： 1. **每次==右边界==向右==扩展一步==**； 2. **检查当前窗口状态**，根据窗口是否满足条件**判断==是否需要收缩左边界==**； 3. **处理当前窗口**； 4. 重复上述过程。 > [!caution] 对于==窗口 `size=0`== 的情况，需要进行==特判==，单独记录模版伪代码如下（仅示意**常规流程**，**并不绝对**）： ```cpp // 下面的循环中, 窗口size至少都为1. // 因此需要特判窗口size为0的情况. // 循环不变量: 每次进入循环前/循环结束后, 区间[i, j)表示当前窗口, j始终指向待处理位置 int i = 0; for (int j = 0; j < n; ++j) { // 扩展右边界, 纳入新元素 include(nums[j]); // 收缩左边界 while (i <= j && ...) { // ? 处理当前区间[i, j] process(i, j); ++i; } // ? 处理当前区间[i, j] process(i, j); } ``` ![[Excalidraw-Solution/滑动窗口_1.excalidraw.svg|377]] %%[[Excalidraw-Solution/滑动窗口_1.excalidraw.md|🖋 Edit in Excalidraw]]%% # 定长的滑动窗口区分两种场景： - （1）**窗口状态** 需 **全量更新** 的情况——例如，对每个窗口，需要**遍历窗口完内所有元素**才能确认状态，本质上是 "**枚举各个窗口**"， $O(n*k)$。 - （2）**窗口状态** 可 **差量更新** 的情况——即窗口状态可通过 "**移除左端旧元素**" & "**加入右端新元素**" 直接得到，**只需处理==边界==**，即真正意义上的 "**滑动**"，$O(n)$。 - 写法一：**窗口从 0 开始扩展**，**达到最大 size 后不变**，随后每次向后滑动；❇️ - 写法二：**初始时==固定窗口 size== 并==根据窗口内状态完成初始化**==，随后每次向后滑动。 ## 场景一：窗口状态需全量更新枚举窗口**左边界**：`for (int i = 0; i + w <= n; ++i)` ； ```cpp int w = size; for (int i = 0; i + w <= n; ++i) { // 枚举窗口左边界 for (int j = 0; j < w; ++j) { process_v(nums[i+j]); // 处理窗口内单项元素 } process(i, i + w -1); //处理整个窗口`[i, i + w - 1]`; } ``` ## 场景二：每次移动后纳入右边界、移除左边界，只需对边界进行处理 ### 写法一 ❇️ > [!caution] 窗口 size 从 0 开始扩展，必须**等==窗口大小满足题目要求==时, 才记录窗口内状态**！不足：**每次窗口移动都要==额外==做两次条件判断**。 ```cpp int w = size; for (int i = 0; i < n; ++i) { // 窗口右边界纳入新元素 include(nums[i]); // 移除当前窗口之外的元素(旧的左边界) if (i >= w - 1) { exclude(nums[i-w]); } // 处理当前窗口 [i-w+1, i] if (i >= w) { process(i-w+1, i); } } ``` ### 写法二 #### 循环不变量定义一：**窗口状态**对应 `[i-w+1, i)` 表示的**大小为 `w-1`** 的窗口 ❇️ 变量 `i` **标识==右边界==**，分成两段： - `for (int i = 0; i < w - 1; ++i)` - `for (int i = w - 1; i < n; ++i)` 这一写法下，代码不会有过多的重复/冗余逻辑。 ```cpp int w = size; // 初始化, 扩展窗口, 这里只纳入了`w-1`项元素 for (int i = 0; i < w - 1; ++i) { include(nums[i]); } // 处理定长窗口 // 循环不变量: 每次进入循环前/结束循环后, 区间[i-w+1, i)表示大小为`w-1`的窗口 for (int i = w - 1; i < n; ++i) { // 纳入新元素, 使得窗口大小变为`w` include(nums[i]); // 处理大小为`w`的窗口[i-w+1, i] process(i-w+1, i); // 收缩左边界, 使[i-w+1, i]表示大小为`w-1`的窗口 exclude(nums[i-w+1]); } ``` 算法流程示意图： ![[Excalidraw-Solution/滑动窗口_2.excalidraw.svg|559]] %%[[Excalidraw-Solution/滑动窗口_2.excalidraw.md|🖋 Edit in Excalidraw]]%% #### 循环不变量定义二：窗口状态对应 `[i-w, i)` 表示的**大小为 `w`** 的窗口 ```cpp int w = size; // 初始化, 扩展窗口, 得到size=w的窗口 for (int i = 0; i < w; ++i) { include(nums[i]); } // 处理首个长度为`w`的定长窗口 process(0, w-1); // 滑动窗口 // 循环不变量: 每次进入循环前/结束循环后, 区间[i-w, i)表示大小为`w`的窗口 for (int i = w; i < n; ++i) { // 纳入新元素 include(nums[i]); // 收缩左边界, 使i、j表示大小为`w`的窗口[i, j] exclude(nums[i-w]); // 处理大小为`w`的窗口[i, j] process(i-w+1, i); } ``` 算法流程示意图： ![[Excalidraw-Solution/滑动窗口_3.excalidraw.svg|600]] %%[[Excalidraw-Solution/滑动窗口_3.excalidraw.md|🖋 Edit in Excalidraw]]%% # 参考资料 # Footnotes