核心目的
滑动窗口技术的主要目的是优化算法。它能将一个通常需要用两层嵌套循环(时间复杂度为 \(O(N^2)\))才能解决的问题,转化为只需一次单循环(时间复杂度为 \(O(N)\)),从而大大提高代码的执行效率。
工作原理
这个技巧就像在数组上有一个大小可变的“窗口”。它通过维护两个指针——左指针 L
和右指针 R
——来框定这个窗口的范围。
- 移动指针:算法通过向前移动这两个指针来“滑动”这个窗口。
- 移动右指针
R
是为了扩大窗口,纳入新的元素。 - 移动左指针
L
是为了缩小窗口,排除旧的元素。
- 移动右指针
- 更新结果:每当窗口滑动到一个新的位置,就根据窗口内的元素重新计算一次结果。
适用场景
滑动窗口并不适用于所有问题。它有一个关键的使用前提:
- 问题通常要求你在一系列连续的子数组(即“窗口”或“区间”)中找到一个最优解(比如最大值、最小值、最短长度等)。
- 最重要的条件是,这些子数组的范围必须具有单调性。也就是说,当区间的起始点向右移动时,其结束点也必须是向右移动(或保持不变)的。用数学语言表达就是:如果两个区间1和2,它们的起始点 \(L_1 < L_2\),那么它们的结束点必须满足 \(R_1 \le R_2\)。这个特性保证了窗口只需向前滑动,而无需回跳。
两种类型
根据窗口的大小是否变化,滑动窗口可以分为:
- 固定大小的滑动窗口:窗口的长度始终不变。
- 可变大小的滑动窗口:窗口的长度根据特定条件动态调整(扩大或缩小)。