一. 定义
- 滑动窗口是一种基于双指针的一种思想,两个指针指向的元素之间形成一个窗口。滑动窗口通过维护一个窗口不断滑动,来更新答案。
- 滑动:说明这个窗口是移动的,也就是移动是按照一定方向来的。
- 窗口:窗口大小并不是固定的,可以不断扩容直到满足一定的条件;也可以不断缩小,直到找到一个满足条件的最小窗口;当然也可以是固定大小。
- 需要注意的细节:
- 那么如何向窗口中添加新元素
- 如何缩小窗口
- 在窗口滑动的哪个阶段更新结果
滑动窗口算法可以用以解决数组/字符串的子元素问题,它可以将嵌套的循环问题,转换为单循环问题,降低时间复杂度。
二. 模板
1. 理论
窗口实际是两个指针之间形成的区域。左右指针轮流前进,窗口大小增增减减,窗口不断向右滑动:- 初始化窗口:在
**序列(字符串/数组)**
中使用双指针中的左右指针技巧,初始化 left = right = 0,把索引闭区间[left, right]
称为一个窗口。 - 寻找可行解:先不断地增加 right 指针扩大窗口 [left, right],直到窗口中的字符串符合要求。
- 优化可行解:停止增加 right,转而不断增加 left 指针缩小窗口
[left, right]
,直到窗口中的字符串不再符合要求。同时,每次增加 left,我们都要更新一轮结果。 - 找到最优解:重复第 2 和第 3 步,直到 right 到达序列的尽头。
- 初始化窗口:在
2. 模板代码
// 情况一:寻找最长的
初始化left,right,result,bestResult
while (右指针没有到结尾) {
窗口扩大,加入right对应元素,更新当前result
while (result不满足要求) {
窗口缩小,移除left对应元素,left右移
}
更新最优结果bestResult
right++;
}
返回bestResult
// 情况二:寻找最短的
初始化left,right,result,bestResult
while (右指针没有到结尾) {
窗口扩大,加入right对应元素,更新当前result
while (result不满足要求) {
更新最优结果bestResult
窗口缩小,移除left对应元素,left右移
}
right++;
}
返回bestResult