面试难点！常用算法技巧之“滑动窗口”

ゝ一世哀愁。 2021-07-24 20:08 525阅读 0赞

## 算法简介 ##

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

可以想象成队列，一端在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

模板只是一个解题思路，具体的题目可能需要具体分析，但是大体框架是不变的。  
记住: 多刷题，多总结，是王道

## 算法示例 ##

1、最长不含重复字符的子字符串

from collections import deque
    
    
    class Solution(object):
        def lengthOfLongestSubstring(self, s):
            """
            :type s: str
            :rtype: int
            """
            if not s:
                return 0
    
            index = 0
            
            # 因为这个滑动窗口需要从一端进，一端出，因此考虑采用队列
            slide_win = deque()
    
            # 因为在滑动过程中需要不断的从窗口中增减元素，因此需要一个变量来保持最大窗口长度
            max_len = 1
    
            while index < len(s):
                # 一个小的优化点：还没有遍历的元素长度加上当前的窗口长度已经小于最大窗口长度，则直接返回结果
                if len(slide_win) + (len(s) - index) <= max_len:
                    return max_len
    
                # 如果当前元素没有在滑动窗口中，则加入，并且窗口扩大
                if s[index] not in slide_win:
                    slide_win.append(s[index])
                    index += 1
                else:
                    # 如果当前元素已经在窗口中有值，则更新最大窗口长度
                    max_len = max(max_len, len(slide_win))
                    # 窗口缩小，对端不变
                    slide_win.popleft()
    
            return max(max_len, len(slide_win))

2、绝对差不超过限制的最长连续子数组

import heapq
    
    
    class Solution(object):
        def longestSubarray(self, nums, limit):
            """
            :type nums: List[int]
            :type limit: int
            :rtype: int
            """
            if not nums:
                return 0
    
            len_nums = len(nums)
    
            # 因为需要比较子列表中的最大差值，即需要知道子列表中的最大值和最小值
            # 因此采用大顶堆和小顶堆
            max_hq = []
            min_hq = []
    
            # 滑动窗口的前后索引
            left = 0
            right = 0
    
            # 在滑动窗口的过程中，更新最大的窗口长度
            max_win = 1
    
            while right < len_nums:
                if len_nums - left <= max_win:
                    return max_win
    
                # 将当前元素及其索引放入堆中，因为python只有小顶堆，因此这里采用负值来模拟大顶堆
                heapq.heappush(max_hq, (-nums[right], right))
                heapq.heappush(min_hq, (nums[right], right))
    
                # 窗口的最大差值
                diff = -max_hq[0][0] - min_hq[0][0]
    
                # 最大差值在允许范围内，窗口后边向前滑动，左边保持不变
                if diff <= limit:
                    right += 1
                    continue
    
                # 最大差值超过范围：
                # 更新最大窗口长度
                max_win = max(max_win, right - left)
    
                # 保证滑动窗口内的最大差值在允许范围内
                while -max_hq[0][0] - min_hq[0][0] > limit:
                    # 去掉大顶堆中在滑动窗口之外的所有最大元素
                    while max_hq[0][1] <= left:
                        heapq.heappop(max_hq)
                    # 去掉小顶堆中在滑动窗口之外的所有最小元素
                    while min_hq[0][1] <= left:
                        heapq.heappop(min_hq)
    
                    left += 1
    
            return max(max_win, right - left)

3、无重复字符的最长子串

from collections import deque
    class Solution(object):
        def lengthOfLongestSubstring(self, s):
            """
            :type s: str
            :rtype: int
            """
            if not s:
                return 0
            
            index = 0
    
            # 因为这里需要从窗口的两端进行元素的增加或减少，因此采用双端队列
            slide_win = deque()
    
            # 题目要求最长子串长度，因此需要在滑动过程中更新最大长度
            max_len = 0
    
            while index < len(s):
                ch = s[index]
    
                # 如果当前元素不在窗口中，则加入窗口
                if ch not in slide_win:
                    slide_win.append(ch)
                    # 窗口的右端向前滑动，左端不变（扩大窗口）
                    index += 1
                else:
                    # 当前元素已经存在窗口中，即表示找到一个可行解，更新最大长度
                    max_len = max(max_len, len(slide_win))
                      Java开发交流君样：756584822
                    # 将窗口中在当前元素值之前的元素全部移除掉，即窗口左端向前滑动，右端不变（缩小窗口）
                    while ch in slide_win:
                        slide_win.popleft()
            
            return max(max_len, len(slide_win))

4、替换后的最长重复字符

class Solution(object):
        def characterReplacement(self, s, k):
            """
            :type s: str
            :type k: int
            :rtype: int
            """
            if not s:
                return 0
            
            # 滑动窗口的左右两端
            left = 0
            right = 0
    
            # 记录每个字符出现的频率
            ch_fre = defaultdict(int)
    
            # 记录字符出现的最大频率
            max_fre = 0
    
            # 在窗口滑动过程中，更新最大长度
            max_len = 0
    
            while right < len(s):
                ch = s[right]
                
                # 当前字符频率加1
                ch_fre[ch] += 1
    
                # 更新字符出现过的最大频率
                max_fre = max(max_fre, ch_fre[ch])
    
                # 如果滑动窗口的长度大于字符能够达到的最大频率
                # 即窗口内不可能出现全是重复的字符，因此需要将窗口的左端向前滑动（缩小窗口）
                if right - left + 1 > max_fre + k:
                    # 滑动出去的字符需要将其频率减1
                    ch_fre[s[left]] -= 1
                    left += 1
    
                # 此时滑动窗口内全是重复字符，更新最大长度值 
                max_len = max(max_len, right - left + 1)
    
                # 滑动窗口的右端向前滑动（扩大窗口）
                right += 1
    //Java开发交流君样：756584822
            return max_len

## 算法总结 ##

滑动窗口算法就是用以解决数组/字符串的子元素问题  
滑动窗口算法可以将嵌套的for循环问题，转换为单循环问题，降低时间复杂度

生命不止坚毅鱼奋斗，有梦想才是有意义的追求  
[给大家推荐一个免费的学习交流群：  
最后，祝大家早日学有所成，拿到满意offer，快速升职加薪，走上人生巅峰。  
Java开发交流君样：756584822][_ _offer_ _ Java_756584822]

[_ _offer_ _ Java_756584822]: https://jq.qq.com/?_wv=1027&k=0IsBuUb0