AJohn Blog

外观

1.1 定长滑动窗口

2283字约8分钟

2024-10-26

1.1.1 基础

定长滑窗套路 我总结成三步：入-更新-出。

  1. 入：下标为 i 的元素进入窗口，更新相关统计量。如果 i<k−1 则重复第一步。
  2. 更新：更新答案。一般是更新最大值/最小值。
  3. 出：下标为 i−k+1 的元素离开窗口，更新相关统计量。 以上三步适用于所有定长滑窗题目。

提示

阿囧说：代码实操中，先滑到k个窗口大小，然后位于s[i+1-k]的字符（想象指针回退k个窗口大小）先出，如果还有新字符则再次进循环，入新字符

  1. 定长子串中元音的最大数目

    class Solution:
def maxVowels(self, s: str, k: int) -> int:
    yuanYin = "aeiou"
    res = 0
    temp = 0
    for i, c in enumerate(s):
        if c in yuanYin:
            temp += 1
        if i + 1 < k:
            continue
        res = max(res, temp)
        if s[i + 1 - k] in yuanYin:
            temp -= 1
    return res

    时间复杂度：O(n)

    空间复杂度：O(1)

  2. 643. 子数组最大平均数 I

    class Solution:
def findMaxAverage(self, nums: List[int], k: int) -> float:
    res, temp = float('-inf'), 0
    for i, num in enumerate(nums):
        temp += num
        if i + 1 < k:
            continue
        res = max(temp, res)
        temp -= nums[i + 1 - k]
    res /= k
    return res

    时间复杂度：O(n)

    空间复杂度：O(1)

  3. 1343. 大小为 K 且平均值大于等于阈值的子数组数目

    class Solution:
def numOfSubarrays(self, arr: List[int], k: int, threshold: int) -> int:
    temp, res = 0, 0
    for i, num in enumerate(arr):
        temp += num
        if i + 1 < k:
            continue
        if temp / k >= threshold:
            res += 1
        temp -= arr[i + 1 - k]
    return res

    时间复杂度：O(n)

    空间复杂度：O(1)

  4. 2090. 半径为 k 的子数组平均值

    我的丑陋解法：

    class Solution:
def getAverages(self, nums: List[int], k: int) -> List[int]:
    res = []
    temp, start = 0, 0
    n = len(nums)
    if n <= 2 * k:
        res = [-1] * n
        return res
    else:
        for _ in range(k):
            res.append(-1)
        for i in range(k):
            start += nums[i]
        for i, num in enumerate(nums):
            start += nums[i + k]
            if i < k:
                continue
            res.append(start // (2 * k + 1))
            start -= nums[i - k]
            if i + k + 1 == n:
                for _ in range(k):
                    res.append(-1)
                break
    return res

    时间复杂度：O(n)

    空间复杂度：O(n)

    tips：但其实i应该滑到窗口的末端而不是中间，代码会简便很多

    class Solution:
def getAverages(self, nums: List[int], k: int) -> List[int]:
    n = len(nums)
    res = [-1] * n
    temp = 0
    for i, num in enumerate(nums):
        temp += num
        if i < 2 * k:
            continue
        res[i - k] = temp // (2 * k + 1)
        temp -= nums[i - 2 * k]
    return res

    时间复杂度：O(n)

    空间复杂度：O(n)

  5. 2379. 得到 K 个黑块的最少涂色次数

    class Solution:
def minimumRecolors(self, blocks: str, k: int) -> int:
    black = 0
    res = float('inf')
    for i, c in enumerate(blocks):
        if c == 'B':
            black += 1
        if i + 1 < k:
            continue
        res = min(k - black, res)
        if blocks[i + 1 - k] == 'B':
            black -= 1
    return res

    时间复杂度：O(n)

    空间复杂度：O(1)

  6. 1052. 爱生气的书店老板

    这题有点意思

    class Solution:
def maxSatisfied(self, customers: List[int], grumpy: List[int], minutes: int) -> int:
    cus1, cus2, temp = 0, 0, 0
    for i, (c, g) in enumerate(zip(customers, grumpy)):
        # 计算不发动技能，有多少顾客满意
        if g == 0:
            cus1 += c
        # temp记录生气导致不满意的顾客
        else:
            temp += c
        if i + 1 < minutes:
            continue
        # 用滑动窗口判断能挽回的客户最大值
        cus2 = max(cus2, temp)
        # 如果退出的窗口是生气的temp才减少
        if grumpy[i + 1 - minutes] == 1:
            temp -= customers[i + 1 - minutes]
    return cus1 + cus2

    时间复杂度：O(n)

    空间复杂度：O(1)

  7. 1461. 检查一个字符串是否包含所有长度为 K 的二进制子串

    巧用集合和切片

    class Solution:
def hasAllCodes(self, s: str, k: int) -> bool:
    set1 = set()
    temp = ''
    for i, c in enumerate(s):
        temp += c
        if i + 1 < k:
            continue
        set1.add(temp)
        temp = temp[1:]
    if len(set1) == 2 ** k:
        return True
    else:
        return False

    时间复杂度：O(nk)

    空间复杂度：O(2k2^k)

  8. 2841. 几乎唯一子数组的最大和

    我的使用集合写法，O(k)，总的时间复杂度是 O((n-k)*k)，不是 O(n)。当 k=n/2 时算法的时间复杂度是 O(n^2)。在力扣通过运行花了7秒，夸张QAQ。

    class Solution:
def maxSum(self, nums: List[int], m: int, k: int) -> int:
    temp_list = []
    temp_sum = 0
    res = 0
    for i, num in enumerate(nums):
        temp_list.append(num)
        if i + 1 < k:
            continue
        if len(set(temp_list)) < m:
            temp_list = temp_list[1:]
            continue
        else:
            temp_sum = sum(temp_list)
            res = max(res, temp_sum)
        temp_list = temp_list[1:]
    return res

    时间复杂度：O(nk)

    空间复杂度：O(k)

    灵神的哈希表写法

    class Solution:
def maxSum(self, nums: List[int], m: int, k: int) -> int:
    ans = 0
    s = sum(nums[:k - 1])  # 先统计 k-1 个数
    cnt = Counter(nums[:k - 1])
    for out, in_ in zip(nums, nums[k - 1:]):
        s += in_  # 再添加一个数就是 k 个数了
        cnt[in_] += 1
        if len(cnt) >= m:
            ans = max(ans, s)
        s -= out  # 下一个子数组不包含 out，移出窗口
        cnt[out] -= 1
        if cnt[out] == 0:
            del cnt[out]
    return ans

    时间复杂度：O(n)

    空间复杂度：O(k)

  9. 2461. 长度为 K 子数组中的最大和

    我的使用集合写法，力扣超时无法通过，时代的眼泪，以后这种类型的题改为哈希表写法了。

    class Solution:
def maximumSubarraySum(self, nums: List[int], k: int) -> int:
    temp, res = 0, 0
    for i, num in enumerate(nums):
        temp += num
        if i + 1 < k:
            continue
        if len(set(nums[i + 1 - k:i + 1])) == k:
            res = max(res, temp)
        temp -= nums[i + 1 - k]
    return res

    时间复杂度：O(nk)

    空间复杂度：O(k)

    哈希表yyds

    class Solution:
def maximumSubarraySum(self, nums: List[int], k: int) -> int:
    temp, res = sum(nums[:k - 1]), 0
    cnt = Counter(nums[:k - 1])
    for in_, out in zip(nums[k - 1:], nums):
        # 入
        temp += in_
        cnt[in_] += 1
        # 更新
        if len(cnt) == k:
            res = max(res, temp)
        # 出
        temp -= out
        cnt[out] -= 1
        if cnt[out] == 0:
            del cnt[out]
    return res

    时间复杂度：O(n)

    空间复杂度：O(k)

  10. 1423. 可获得的最大点数

    这题很有点意思

    解法一：逆向思维：求剩下的牌点数最小之和，剩下的牌一定是连续的，可以视为滑动窗口

    class Solution:
def maxScore(self, cardPoints: List[int], k: int) -> int:
    n = len(cardPoints)
    m = n - k
    min_s = s = sum(cardPoints[:m])
    for i in range(m, n):
        s += cardPoints[i] - cardPoints[i - m]
        min_s = min(min_s, s)
    return sum(cardPoints) - min_s

    时间复杂度：O(n)

    空间复杂度：O(1)

    解法二：可以把后k个元素和前k个元素组成一个新的列表

    class Solution:
def maxScore(self, cardPoints: List[int], k: int) -> int:
    res, temp = 0, 0
    nums = cardPoints[-k:] + cardPoints[:k]
    for i, num in enumerate(nums):
        temp += num
        if i + 1 < k:
            continue
        res = max(res, temp)
        temp -= nums[i + 1 -k]
    return res

    时间复杂度：O(k)

    空间复杂度：O(k)

    同解法二，不使用列表存储，枚举所有情况取最大值

    class Solution:
def maxScore(self, cardPoints: List[int], k: int) -> int:
    res = temp = sum(cardPoints[:k])
    for i in range(1, k + 1):
        temp += cardPoints[-i] - cardPoints[k - i]
        res = max(res, temp)
    return res

    时间复杂度：O(k)

    空间复杂度：O(1)

  11. 1652. 拆炸弹

    拆不了一点，没看懂

    class Solution:
def decrypt(self, code: List[int], k: int) -> List[int]:
    n = len(code)
    res = [0] * n
    r = k + 1 if k > 0 else n
    k = abs(k)
    temp = sum(code[r - k:r])
    for i in range(n):
        res[i] = temp
        temp += code[(r) % n] - code[(r - k) % n]
        r += 1
    return res

    时间复杂度：O(n)

    空间复杂度：O(1)

  12. 1297. 子串的最大出现次数

    汗流浃背了，使用词典的滑动窗口

    class Solution:
def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
    dic = defaultdict(int)
    for i in range(len(s) - minSize + 1):
        # 因为这里是字符串，所以可以通过切片快速构造滑动窗口
        temp = s[i: i + minSize]
        if len(set(temp)) <= maxLetters:
            dic[temp] += 1
    return max(dic.values()) if dic else 0

    时间复杂度：O(n * m)，其中 n 是字符串 s 的长度, m 是minSize

    空间复杂度：O(k)，其中 k 是字典中存储的不同子串的数量

    • dic = defaultdict(int)和dic = {}的区别： defaultdict(int) 会自动为新键分配默认值 0（因为 int() 的返回值是 0）。当你访问一个不存在的键时，不会引发 KeyError，而是返回 0。普通字典在访问不存在的键时，会抛出 KeyError

    • defaultdict和Counter的区别：

      • defaultdict：用于创建带有默认值的字典。可以指定默认值的类型（如 int, list, set 等）。 适用于需要管理键值对并且可能在访问时需要默认值的情况。
      • Counter：特别设计用于计数对象的出现次数。它自动将新键的计数初始化为 0，并在每次增加时更新计数。适用于频率计数和统计

    • 词典是一种基于哈希表的实现，Counter也是基于字典实现的，专注于计数

    使用Counter的滑动窗口

    class Solution:
def maxFreq(self, s: str, maxLetters: int, minSize: int, maxSize: int) -> int:
    cnt = Counter()
    temp = ''
    for i, c in enumerate(s):
        temp += c
        if i + 1 < minSize:
            continue
        if len(set(temp)) <= maxLetters:
            cnt[temp] += 1
        temp = temp[1:]
    return max(cnt.values()) if cnt else 0

    时间复杂度：O(n * m)，其中 n 是字符串 s 的长度, m 是minSize

    空间复杂度：O(m)，其中 m 是minSize

1.1.2 进阶（选做）

1.1.3 其他（选做）

Copyright © 2024 AJohn