滑动窗口专项训练

算法简介

滑动窗口，就是有一个大小可变的窗口，左右两端方向一致的向前滑动（右端固定，左端滑动；左端固定，右端滑动），也可以想象为队列，一端在push元素，另外一段在pop元素，如下所示：

假设有数组[a,b,c,d,e,f,g,h]
一个大小为3的滑动窗口在其中滑动，则有：
[a,b,c]
[b,c,d]
[c,d,e]
...
[f,g,h]

滑动窗口通常用在字符创或者列表的算法问题中，常出现的关键词如下：

满足XXX条件（计算结果，出现次数，同时包含）
最长/最短
子串/子数组/子序列
eg：长度最小的子数组、无重复字符的最长子串、最小覆盖子串等

算法思想

在序列中使用双指针中的左右指针技巧，初始化left=right=0，把索引闭区间[left,right]称为一个窗口。
先不断地增加right指针扩大窗口[left,right]，直到窗口中的序列符合要求。
此时，停止增加right，转而不断增加left指针缩小窗口[left,right]，直到窗口中的序列不再符合要求。同时，每次增加left前，都要更新一轮结果。

总结以上步骤：第二步相当于在寻找一个可行解，然后在第三步优化这个可行解，最终找到最优解。左右指针轮流前进，窗口大小增增减减，窗口不断向右滑动。

算法模板

单层循环

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

双层循环

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

算法案例

剑指Offer48. 最长不含重复字符的子字符串

题目链接：https://leetcode.cn/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/description/

题解

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n=len(s)

        lookup=set()

        left=0
        right=0

        max_len=0
        cur_len=0

        #一层循环，寻找可行解
        while right<=n-1:
            if s[right] not in lookup:
                lookup.add(s[right])
                cur_len+=1
                right+=1
            #固定右指针，移动左指针，更新最优解
            else:
                max_len=max(max_len,cur_len)
                lookup.remove(s[left])
                left+=1
                cur_len-=1

        max_len=max(max_len,cur_len)

        return max_len

Leecode.1438 绝对差不超过限制的最长连续子数组

题目链接：https://leetcode.cn/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/

题解

class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        if not nums:
            return 0

        len_nums=len(nums)

        #因为需要比较子列表中的最大差值，所以需要知道字列表的最大、最小值
        #采用单调队列
        queMax,queMin=deque(),deque()

        # 滑动窗口的前后索引
        left=0
        right=0

        #结果
        ret=0

        #滑动窗口长度
        max_win=1
        while right<len_nums:

            #将当前元素及其索引放入单调队列中
            while queMax and queMax[-1]<nums[right]:
                queMax.pop()
            while queMin and queMin[-1]>nums[right]:
                queMin.pop()

            queMax.append(nums[right])
            queMin.append(nums[right])

            #如果数组内的最大值和最小值之差不满足limit要求
            while queMax and queMin and queMax[0]-queMin[0]>limit:
                #如果左指针对应当前的最大值或者最小值
                if nums[left]==queMin[0]:
                    queMin.popleft()
                if nums[left]==queMax[0]:
                    queMax.popleft()
                left+=1

            ret=max(ret,right-left+1)
            right+=1
        return ret

Leecode.151 反转字符串中的单词

题目链接：https://leetcode.cn/problems/reverse-words-in-a-string/

题解

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        num=[0]*26
        n=len(s)

        max_len=left=right=0

        while right<n:
            #更新当前字母对应的计数
            num[ord(s[right])-ord('A')]+=1
            #判断最大长度是否为当前字母的计数
            max_len=max(max_len,num[ord(s[right])-ord('A')])
            #如果右-左区间的字母计数-最大长度字母的计数>k个，即k次操作无法将区间内全部字母统一
            if right-left+1-max_len>k:
                #移动左侧指针，减少对应的字母计数
                num[ord(s[left])-ord('A')]-=1
                left+=1
            right+=1
        return right-left