算法—滑动窗口

滑动窗口

算法简介
滑动窗口，顾名思义，就是有一个大小可变的窗口，左右两端方向一致的向前滑动（右端固定，左端滑动；左端固定，右端滑动）。

可以想象成队列，一端在push元素，另一端在pop元素，如下所示：

假设有数组[a b c d e f g h]
一个大小为3的滑动窗口在其上滑动，则有:
[a b c]
[b c d]
[c d e]
[d e f]
[e f g]
[f g h]
适用范围
1、一般是字符串或者列表
2、一般是要求最值（最大长度，最短长度等等）或者子序列
算法思想
1、在序列中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引闭区间 [left, right] 称为一个窗口。
2、先不断地增加 right 指针扩大窗口 [left, right]，直到窗口中的序列符合要求。
3、此时，停止增加 right，转而不断增加 left 指针缩小窗口 [left, right]，直到窗口中的序列不再符合要求。同时，每次增加 left前，都要更新一轮结果。
4、重复第 2 和第 3 步，直到 right 到达序列的尽头。
思路其实很简单：第 2 步相当于在寻找一个可行解，然后第 3 步在优化这个可行解，最终找到最优解。左右指针轮流前进，窗口大小增增减减，窗口不断向右滑动。

算法模板
1、单层循环

def template():
# 初始化滑动窗口两端
left = right = 0
# 序列及序列长度
seq, seq_len = xx, xx

# 滑动窗口序列
slide_win = []

# 结果值
rst = xx

while right < seq_len:
    slide_win.append(seq[right])
    # 还没找到一个可行解
    if not avaliable(slide_win):
        # 扩大窗口
        right += 1
    else:
        # 找到一个可行解，更新结果值
        rst = update()
        # 缩小窗口
    left += 1

2、双层循环

def template():
# 初始化滑动窗口两端
left = right = 0
# 序列及序列长度
seq, seq_len = xx, xx

# 滑动窗口序列
slide_win = []

# 结果值
rst = xx

while right < seq_len:
    slide_win.append(seq[right])
    # 还没找到一个可行解
    if not avaliable(slide_win):
        # 扩大窗口
        right += 1
        continue
        
        # 循环更新可行解
        while avaliable(slide_win):
            # 找到一个可行解，更新结果值
            rst = update()
            # 缩小窗口
    left += 1

模板只是一个解题思路，具体的题目可能需要具体分析，但是大体框架是不变的。