三道滑动窗口与子串题的 Python 写法

真正适合这题的是单调队列。它的关键不是'队列'本身，而是始终把窗口内可能成为最大值的下标留在队列里，队首永远是当前窗口最大值的位置。元素进来时把比它小的尾部元素删掉，元素滑出窗口时再检查队首是否过期。

from typing import List
from collections import deque

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        ans = []
        q = deque()
        for i, x in enumerate(nums):
            # 入
            while q and nums[q[-1]] <= x:
                q.pop()
            q.append(i)
            # 出
            if i - q[0] >= k:
                q.popleft()
            # 记录
            if i >= k - 1:
                ans.append(nums[q[0]])
        return ans

三、76. 最小覆盖子串

这题还是滑动窗口，不过重点变成了'窗口是否已经覆盖了 t'。Counter 的好处在于可以直接比较两个计数器，不用自己写一套字符数量判断，代码会干净很多。

from typing import List
from collections import Counter

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        ansLeft, ansRight = -1, len(s)
        cntS = Counter()
        cntT = Counter(t)
        left = 0
        for right, word in enumerate(s):
            cntS[word] += 1
            while cntS >= cntT:
                if right - left < ansRight - ansLeft:
                    ansLeft, ansRight = left, right
                cntS[s[left]] -= 1
                left += 1
        return "" if ansLeft < 0 else s[ansLeft:ansRight+1]

这三题放在一起看，核心其实都不复杂：前缀和处理'区间统计'，单调队列处理'窗口最值'，计数器处理'窗口覆盖'。题目换壳很多，套路就这几种，写熟了以后基本不会卡在思路上。