滑動窗口是一種常用的算法技巧,可以有效解決一些字符串、數列等問題。
在Python中,我們可以使用雙指針來實現滑動窗口。具體來說,我們設定左右指針left和right,表示窗口的左右端點,然后通過移動這兩個指針來實現滑動窗口。
def sliding_window(s): n = len(s) left, right = 0, 0 res = 0 while right< n: # 移動右指針 window.add(s[right]) right += 1 while window.size() >k: # 移動左指針 window.remove(s[left]) left += 1 # 更新答案 res = max(res, right - left) return res
在上述代碼中,我們使用了一個set類型的window來維護滑動窗口。具體來說,我們將當前窗口內的元素都添加到set中,然后動態調整左右窗口的大小,直到滿足條件為止。
在實際編程中,我們還可以使用deque數據結構來實現滑動窗口。具體來說,我們可以將deque中存儲的元素作為窗口內的元素,然后通過從前端彈出元素和從后端添加元素來動態調整窗口的大小。
from collections import deque def sliding_window(s): n = len(s) left, right = 0, 0 res = 0 window = deque() while right< n: # 移動右指針 window.append(s[right]) right += 1 while len(window) >k: # 移動左指針 window.popleft() left += 1 # 更新答案 res = max(res, right - left) return res
在實際編程中,我們需要根據具體問題選擇不同的實現方法。通過靈活應用滑動窗口算法,我們可以解決很多復雜的問題,提升自己的算法水平。