算法簡介

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

可以想象成隊(duì)列，一端在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 = xxwhile right < seq_len:slide_win.append(seq[right])# 還沒找到一個可行解if not avaliable(slide_win):# 擴(kuò)大窗口right += 1else:# 找到一個可行解，更新結(jié)果值rst = update()# 縮小窗口left += 1

2、雙層循環(huán)

def template():# 初始化滑動窗口兩端left = right = 0# 序列及序列長度seq, seq_len = xx, xx# 滑動窗口序列slide_win = []# 結(jié)果值rst = xxwhile right < seq_len:slide_win.append(seq[right])# 還沒找到一個可行解if not avaliable(slide_win):# 擴(kuò)大窗口right += 1continue# 循環(huán)更新可行解while avaliable(slide_win):# 找到一個可行解，更新結(jié)果值rst = update()# 縮小窗口left += 1

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

算法示例

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

from collections import dequeclass Solution(object):def lengthOfLongestSubstring(self, s):""":type s: str:rtype: int"""if not s:return 0index = 0# 因?yàn)檫@個滑動窗口需要從一端進(jìn)，一端出，因此考慮采用隊(duì)列slide_win = deque()# 因?yàn)樵诨瑒舆^程中需要不斷的從窗口中增減元素，因此需要一個變量來保持最大窗口長度max_len = 1while 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 += 1else:# 如果當(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 heapqclass Solution(object):def longestSubarray(self, nums, limit):""":type nums: List[int]:type limit: int:rtype: int"""if not nums:return 0len_nums = len(nums)# 因?yàn)樾枰容^子列表中的最大差值，即需要知道子列表中的最大值和最小值# 因此采用大頂堆和小頂堆max_hq = []min_hq = []# 滑動窗口的前后索引left = 0right = 0# 在滑動窗口的過程中，更新最大的窗口長度max_win = 1while right < len_nums:if len_nums - left <= max_win:return max_win# 將當(dāng)前元素及其索引放入堆中，因?yàn)閜ython只有小頂堆，因此這里采用負(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 += 1continue# 最大差值超過范圍：# 更新最大窗口長度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 += 1return 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 0index = 0# 因?yàn)檫@里需要從窗口的兩端進(jìn)行元素的增加或減少，因此采用雙端隊(duì)列slide_win = deque()# 題目要求最長子串長度，因此需要在滑動過程中更新最大長度max_len = 0while index < len(s):ch = s[index]# 如果當(dāng)前元素不在窗口中，則加入窗口if ch not in slide_win:slide_win.append(ch)# 窗口的右端向前滑動，左端不變（擴(kuò)大窗口）index += 1else:# 當(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 = 0right = 0# 記錄每個字符出現(xiàn)的頻率ch_fre = defaultdict(int)# 記錄字符出現(xiàn)的最大頻率max_fre = 0# 在窗口滑動過程中，更新最大長度max_len = 0while right < len(s):ch = s[right]# 當(dāng)前字符頻率加1ch_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:# 滑動出去的字符需要將其頻率減1ch_fre[s[left]] -= 1left += 1# 此時滑動窗口內(nèi)全是重復(fù)字符，更新最大長度值 max_len = max(max_len, right - left + 1)# 滑動窗口的右端向前滑動（擴(kuò)大窗口）right += 1 //Java開發(fā)交流君樣：756584822return max_len

算法總結(jié)

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

最后，祝大家早日學(xué)有所成，拿到滿意offer

總結(jié)

以上是生活随笔為你收集整理的面试难点！常用算法技巧之“滑动窗口”的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。