算法簡介

滑動窗口，顧名思義，就是有一個大小可變的窗口，左右兩端方向一致的向前滑動（右端固定，左端滑動；左端固定，右端滑動）。

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

假設(shè)有數(shù)組[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，把索引閉區(qū)間 [left, right] 稱為一個窗口。
• 2、先不斷地增加 right 指針擴(kuò)大窗口 [left, right]，直到窗口中的序列符合要求。
• 3、此時，停止增加 right，轉(zhuǎn)而不斷增加 left 指針縮小窗口 [left, right]，直到窗口中的序列不再符合要求。同時，每次增加 left前，都要更新一輪結(jié)果。
• 4、重復(fù)第 2 和第 3 步，直到 right 到達(dá)序列的盡頭。
  思路其實(shí)很簡單：第 2 步相當(dāng)于在尋找一個可行解，然后第 3 步在優(yōu)化這個可行解，最終找到最優(yōu)解。左右指針輪流前進(jìn)，窗口大小增增減減，窗口不斷向右滑動。

算法模板

1、單層循環(huán)

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

    # 滑動窗口序列
    slide_win = []

    # 結(jié)果值
    rst = xx

    while right < seq_len:
        slide_win.append(seq[right])
        # 還沒找到一個可行解
        if not avaliable(slide_win):
            # 擴(kuò)大窗口
            right += 1
        else:
            # 找到一個可行解，更新結(jié)果值
            rst = update()
            # 縮小窗口
            left += 1

2、雙層循環(huán)

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

    # 滑動窗口序列
    slide_win = []

    # 結(jié)果值
    rst = xx

    while right < seq_len:
        slide_win.append(seq[right])
        # 還沒找到一個可行解
        if not avaliable(slide_win):
            # 擴(kuò)大窗口
            right += 1
            continue

        # 循環(huán)更新可行解
        while avaliable(slide_win):
            # 找到一個可行解，更新結(jié)果值
            rst = update()
            # 縮小窗口
            left += 1

模板只是一個解題思路，具體的題目可能需要具體分析，但是大體框架是不變的。
記住: 多刷題，多總結(jié)，是王道

算法示例

1、最長不含重復(fù)字符的子字符串

from collections import deque


class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s:
            return 0

        index = 0
        
        # 因為這個滑動窗口需要從一端進(jìn)，一端出，因此考慮采用隊列
        slide_win = deque()

        # 因為在滑動過程中需要不斷的從窗口中增減元素，因此需要一個變量來保持最大窗口長度
        max_len = 1

        while index < len(s):
            # 一個小的優(yōu)化點(diǎn)：還沒有遍歷的元素長度加上當(dāng)前的窗口長度已經(jīng)小于最大窗口長度，則直接返回結(jié)果
            if len(slide_win) + (len(s) - index) <= max_len:
                return max_len

            # 如果當(dāng)前元素沒有在滑動窗口中，則加入，并且窗口擴(kuò)大
            if s[index] not in slide_win:
                slide_win.append(s[index])
                index += 1
            else:
                # 如果當(dāng)前元素已經(jīng)在窗口中有值，則更新最大窗口長度
                max_len = max(max_len, len(slide_win))
                # 窗口縮小，對端不變
                slide_win.popleft()

        return max(max_len, len(slide_win))

2、絕對差不超過限制的最長連續(xù)子數(shù)組

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

            # 將當(dāng)前元素及其索引放入堆中，因為python只有小頂堆，因此這里采用負(fù)值來模擬大頂堆
            heapq.heappush(max_hq, (-nums[right], right))
            heapq.heappush(min_hq, (nums[right], right))

            # 窗口的最大差值
            diff = -max_hq[0][0] - min_hq[0][0]

            # 最大差值在允許范圍內(nèi)，窗口后邊向前滑動，左邊保持不變
            if diff <= limit:
                right += 1
                continue

            # 最大差值超過范圍：
            # 更新最大窗口長度
            max_win = max(max_win, right - left)

            # 保證滑動窗口內(nèi)的最大差值在允許范圍內(nèi)
            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、無重復(fù)字符的最長子串

from collections import deque
class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s:
            return 0
        
        index = 0

        # 因為這里需要從窗口的兩端進(jìn)行元素的增加或減少，因此采用雙端隊列
        slide_win = deque()

        # 題目要求最長子串長度，因此需要在滑動過程中更新最大長度
        max_len = 0

        while index < len(s):
            ch = s[index]

            # 如果當(dāng)前元素不在窗口中，則加入窗口
            if ch not in slide_win:
                slide_win.append(ch)
                # 窗口的右端向前滑動，左端不變（擴(kuò)大窗口）
                index += 1
            else:
                # 當(dāng)前元素已經(jīng)存在窗口中，即表示找到一個可行解，更新最大長度
                max_len = max(max_len, len(slide_win))
                  Java開發(fā)交流君樣：756584822
                # 將窗口中在當(dāng)前元素值之前的元素全部移除掉，即窗口左端向前滑動，右端不變（縮小窗口）
                while ch in slide_win:
                    slide_win.popleft()
        
        return max(max_len, len(slide_win))

4、替換后的最長重復(fù)字符

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

        # 記錄每個字符出現(xiàn)的頻率
        ch_fre = defaultdict(int)

        # 記錄字符出現(xiàn)的最大頻率
        max_fre = 0

        # 在窗口滑動過程中，更新最大長度
        max_len = 0

        while right < len(s):
            ch = s[right]
            
            # 當(dāng)前字符頻率加1
            ch_fre[ch] += 1

            # 更新字符出現(xiàn)過的最大頻率
            max_fre = max(max_fre, ch_fre[ch])

            # 如果滑動窗口的長度大于字符能夠達(dá)到的最大頻率
            # 即窗口內(nèi)不可能出現(xiàn)全是重復(fù)的字符，因此需要將窗口的左端向前滑動（縮小窗口）
            if right - left + 1 > max_fre + k:
                # 滑動出去的字符需要將其頻率減1
                ch_fre[s[left]] -= 1
                left += 1

            # 此時滑動窗口內(nèi)全是重復(fù)字符，更新最大長度值 
            max_len = max(max_len, right - left + 1)

            # 滑動窗口的右端向前滑動（擴(kuò)大窗口）
            right += 1
//Java開發(fā)交流君樣：756584822
        return max_len

算法總結(jié)

滑動窗口算法就是用以解決數(shù)組/字符串的子元素問題
滑動窗口算法可以將嵌套的for循環(huán)問題，轉(zhuǎn)換為單循環(huán)問題，降低時間復(fù)雜度

生命不止堅毅魚奮斗，有夢想才是有意義的追求
給大家推薦一個免費(fèi)的學(xué)習(xí)交流群：
最后，祝大家早日學(xué)有所成，拿到滿意offer，快速升職加薪，走上人生巔峰。
Java開發(fā)交流君樣：756584822