滑动窗口

NO.239 滑动窗口最大值
deque = double-end queue双端队列
collections是python的标准库，数据结构的常用模块，collections包含了一些特殊容器：
deque()双向队列：可以快速的在队列头部和尾部添加、删除元素
Counter()计数器：dict的子类，计算可hash对象
defaultdict()默认字典：dict的子类，可以调用提供默认值的函数
OrderedDict()有序字典：dict的子类，可以记住元素的添加顺序
namedtuple()可命名元组：可以创建包含名称的元组

deque()是栈和队列的一种广义实现，double-end queue，能在deque的两端插入和删除元素
append()：从右端插入元素
appendleft()：从左端插入元素
extend()：从右端逐个添加可迭代对象（如列表，元组，字典，字符串）
extendleft()：从左端逐个添加可迭代对象
pop():移除列表中的元素（默认最右边），并返回该元素的值，如果没有元素，将会报indexError
popleft():移除列表最左端的元素
count()：统计列表中元素的个数
inseer(index, obj)：在指定位置插入元素
rotate(n):从右侧翻转n步，如果是负数则从左侧翻转
clear()：将deque()中的元素全部清除，最后长度为0
remove()：移除第一次出现的元素，如果没有找到，则报valueError
maxlen():只读属性，deque()的最大限度长度，如果没有就返回NOne，当长度超过限制时，另一边的项会自动删除。

enumerate():用于将一个可遍历的数据对象（如列表、元组、字符串）组合为一个索引序列，同时列出数据和下标
enumerate(iterable, start):两个参数，一个可迭代对象和一个可选的起始索引值。
iterable:一个可迭代对象，如列表、元组等
start():计数的起始值，默认为为0，start参数自定义索引的起始值

法一：在两端插入和删除，使用双端队列，并且需要保持单调性；双端队列里保存的是索引
该问题可分为三步：
1、入： 先判断：对于双端队列里小于当前值的，全部删除while q and nums[q[-1]] < num： q.pop()，然后将当前值的索引添加到队列里q.append(i)
2、出：如果队列长度已经大于窗口k，则删除队首元素if i - q[0] + 1 > k: q.popleft()
3、记录答案：if i >= k-1: ans.append(nums[q[0]])

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        ans = []
        q = deque()
        for i, num in enumerate(nums):
            #1、进入，先判断，队列里小于当前值的，全部删除，注意队列里存的是值的索引
            while q and nums[q[-1]] <= num:
                q.pop()
            q.append(i)
            #2、出，对于已经超过窗口的数，直接删除
            if i - q[0] + 1 > k:
                q.popleft()
            #3、这里最难理解，序列从0开始，所以只有i >= k-1时才开始存储，前面的不是一个完整窗口，再往后前面操作完成第一个值是最大值，因为双端队列保持了单调性
            if i >= k -1:
                ans.append(nums[q[0]])     
        return ans

法二：暴力解法：枚举所有窗口，找到每个窗口的最大值，然后将每个窗口最大值放入输出列表中，一共n-k+1个滑动窗口
class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        if n * k == 0:
            return []        
        ans = []
        for i in range(0, n-k+1):
            max_val = - sys.maxsize - 1
            for j in range(i, i + k):
                max_val = max(max_val, nums[j])   
            ans.append(max_val)
        return ans


NO.76 最小覆盖子串
Counter()计数器：是collections的一个类，可以将元素数量统计，然后计数并返回一个字典，键为元素，值为元素个数。
Counter的几个特殊方法
most_common:counter中n个最大数目的元素，如果不设置n，则返回其中的所有元素，数目相同的将会选择出现早的元素
update():更新计数器，将另一个可迭代对象的元素加入到计数器中
counter支持加法+、减法—-、交集&、并集|
从Python 3.10开始，Counter对象间开始支持常见的比较运算符，如大于，则左侧对应的值都大于右侧的值时，结果为True。

法一：枚举s子串的右端点，如果子串涵盖t，就不断移动左端点left直到不涵盖为止，在移动过程中更新最短子串的左右端点。
初始化ansleft = -1, ansright = len(s)
建立哈希表统计t中每个字母出现的次数
初始化left = 0，建立一个空哈希表统计s子串红每个字母出现的次数
遍历s，枚举当前子串右端点right，把s[right]出现次数+1
遍历s中每个字母及其出现次数，如果出现次数>= t 中字母出现次数：
如果right - left < ansright - ansleft，说明找到了更短的子串，将ansleft, ansright更新为left, right
count_S[s[left]]出现次数减一，尝试破坏条件
左端点右移,即left+1
重复前面三步，直到count_s不能完全覆盖count_t
最后，如果ansleft < 0，说明没有找到更小的区间，返回空字符串，否则返回ansleft到ansright之间的字串
def minWindow(self, s: str, t: str) -> str:
        ans_left, ans_right = -1, len(s)
        count_t = Counter(t)
        count_s = Counter()

        left = 0
        for right, c in enumerate(s):
            count_s[c] += 1
            while count_s >= count_t:
                if right - left < ans_right - ans_left:
                    ans_left, ans_right = left, right
                count_s[s[left]] -= 1
                left += 1
        return '' if ans_left < 0 else s[ans_left: ans_right + 1]

法二：
整体方法类似法一，但是有所优化，如果每次判断滑动窗口是否包含T的所有元素，都去遍历need所有元素是否小于等于0，那么比较复杂，
可以额外维护一个遍历neeCount记录所需元素总数量，当碰到一个所需元素，不仅need[c]减少1，而且needCount减少1，通过needCount就可以知道是否满足条件，而不用遍历字典。
def minWindow(self, s: str, t: str) -> str:
        need = Counter(t)
        needCount = len(t)

        ans_left, ans_right =-1, len(s) + 1
        left = 0
        for right, c in enumerate(s):
            if need[c] > 0: #只有当进入的字符还需要时，count才减一，对于已经足够多的字符，计数不减
                needCount -= 1
            need[c] -= 1#新进一个，该字符对应的数字减一

            if needCount == 0:#当滑动窗口已经完全覆盖t的所有字符，即t的所有字符都已经在窗口里面
                while True:#排除多余元素，每排除一个元素，need[c]+=1,左指针右移，知道没有多余元素，当need[c] == 0时，说明当前元素不存在多的，跳出此次循环
                    c = s[left]
                    if need[c] == 0:
                        break
                    need[c] += 1 #如果上面的不成立，说明还存在多余的字符，继续遍历，直至没有多余
                    left += 1
                if right - left < ans_right - ans_left: #当一次字符need[c] == 0时，记录当前的最小覆盖子串下标
                    ans_left, ans_right = left, right
                need[s[left]] += 1 #一次遍历结束，最左侧的字符被移除，破坏窗口条件，此时最左侧的字符需要数+1，
                needCount += 1  #需要的字符数+1
                left += 1 #左指针右移

        return "" if ans_left < 0 else s[ans_left: ans_right + 1]

NO.424 替换后的最长重复字符
这道题是典型的滑动窗口问题，当k=0时，此题目就变成了求解字符串中最长连续子串长度
滑动窗口求解过程：窗口初始宽带为1——出现更长的连续序列，宽度+1——当前没有更长的序列，整个窗口平移——如果发现更长的序列，窗口宽度+1
窗口从左至右不断扩张/滑动，当窗口得到末尾时运算结束。
此题中，当k>0时，如何判断一个字符改变k个字符能够编程一个连续串？
窗口中字符串出现次数最多的字母个数+K，如果大于窗口长度，就满足条件
窗口扩张：left不变，right+1
窗口滑动：left+1, right+1
用一个变量记录滑动窗口内相同字符出现的历史最大次数，通过判断right-left+1是否大于history+K来决定窗口是否滑动，否则扩张。

def characterReplacement(self, s: str, k: int) -> int:
        count = Counter()
        history_max = 0 #记录历史最大窗口同字符次数
        left = 0
        for right in range(len(s)):
            count[s[right]] += 1 
            history_max = max(history_max, count[s[right]])
            if right - left + 1 > history_max + k: #不够大时，窗口滑动，破坏原来的条件，整体向右移
                count[s[left]] -= 1
                left += 1
        return right - left + 1 #返回最长长度

NO.567 字符串的排列
s1的排列之一是s2的子串，意味着s2的子串长度和s1相等，并且其中的每个字符的数量都完全相等
用一个和s1长度相等的滑动窗口，在s2上从左向右滑动，判断字符数量是否相等
n1 = len(s1)
        n2 = len(s2)
        count_s1 = Counter(s1)
        count_s2 = Counter(s2[:n1-1])
        for i in range(n1-1, n2):
            count_s2[s2[i]] += 1
            if count_s2 == count_s1:
                return True
            count_s2[s2[i-n1+1]] -= 1
        return False