定长滑窗

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

给你字符串 s 和整数 k 。

请返回字符串 s 中长度为 k 的单个子字符串中可能包含的最大元音字母数。

英文中的 元音字母 为（a, e, i, o, u）。

示例 1：

输入：s = “abciiidef”, k = 3

输出：3

解释：子字符串 “iii” 包含 3 个元音字母。

示例 2：

输入：s = “aeiou”, k = 2

输出：2

解释：任意长度为 2 的子字符串都包含 2 个元音字母。

示例 3：

输入：s = “leetcode”, k = 3

输出：2

解释：“lee”、“eet” 和 “ode” 都包含 2 个元音字母。

示例 4：

输入：s = “rhythms”, k = 4

输出：0

解释：字符串 s 中不含任何元音字母。

示例 5：

输入：s = “tryhard”, k = 4

输出：1

提示：

• 1 <= s.length <= 10^5
• s 由小写英文字母组成
• 1 <= k <= s.length

我的答案:

func maxVowels(str string, k int) int {
	ans := 0
	cur := 0
	for i, s := range str {
		if vowels[byte(s)] {
			cur++
		}
		if i < k {
			if cur > ans {
				ans = cur
			}
			continue
		}
		if vowels[str[i-k]] {
			cur--
		}
		if cur > ans {
			ans = cur
		}
	}
	return ans
}

var vowels = map[byte]bool{
	'a': true,
	'e': true,
	'i': true,
	'o': true,
	'u': true,
}

题解答案:

定长滑窗套路

我总结成三步：入-更新-出。

• 入：下标为 i 的元素进入窗口，更新相关统计量。如果 i<k−1 则重复第一步。
• 更新：更新答案。一般是更新最大值/最小值。
• 出：下标为 i−k+1 的元素离开窗口，更新相关统计量。

func maxVowels(s string, k int) (ans int) {
    vowel := 0
    for i, in := range s {
        // 1. 进入窗口
        if in == 'a' || in == 'e' || in == 'i' || in == 'o' || in == 'u' {
            vowel++
        }
        if i < k-1 { // 窗口大小不足 k
            continue
        }
        // 2. 更新答案
        ans = max(ans, vowel)
        // 3. 离开窗口
        out := s[i-k+1]
        if out == 'a' || out == 'e' || out == 'i' || out == 'o' || out == 'u' {
            vowel--
        }
    }
    return
}

643. 子数组最大平均数 I

简单

给你一个由 n 个元素组成的整数数组 nums 和一个整数 k 。

请你找出平均数最大且 长度为 k 的连续子数组，并输出该最大平均数。

任何误差小于 10-5 的答案都将被视为正确答案。

示例 1：

输入：nums = [1,12,-5,-6,50,3], k = 4

输出：12.75

解释：最大平均数 (12-5-6+50)/4 = 51/4 = 12.75

示例 2：

输入：nums = [5], k = 1

输出：5.00000

提示：

• n == nums.length
• 1 <= k <= n <= 105
• -104 <= nums[i] <= 104

func findMaxAverage(nums []int, k int) float64 {
    ans := math.MinInt
    cur := 0
    for i, n := range nums {
        cur += n
        if i < k-1 {
            continue
        }
        if cur > ans {
            ans = cur
        }
        cur -= nums[i-k+1]
    }
    return float64(ans) / float64(k)
}

贯彻落实了定长滑窗套路: 入-更新-出

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

给你一个整数数组 arr 和两个整数 k 和 threshold 。

请你返回长度为 k 且平均值大于等于 threshold 的子数组数目。

示例 1：

输入：arr = [2,2,2,2,5,5,5,8], k = 3, threshold = 4

输出：3

解释：子数组 [2,5,5],[5,5,5] 和 [5,5,8] 的平均值分别为 4，5 和 6 。其他长度为 3 的子数组的平均值都小于 4 （threshold 的值)。

示例 2：

输入：arr = [11,13,17,23,29,31,7,5,2,3], k = 3, threshold = 5

输出：6

解释：前 6 个长度为 3 的子数组平均值都大于 5 。注意平均值不是整数。

提示：

• 1 <= arr.length <= 105
• 1 <= arr[i] <= 104
• 1 <= k <= arr.length
• 0 <= threshold <= 104

我的答案:

func numOfSubarrays(arr []int, k int, threshold int) int {
    ans := 0
    cur := 0
    for i, n := range arr {
        cur += n
        if i < k-1 {
            continue
        }
        if cur/k >= threshold {
            ans++
        }
        cur -= arr[i-k+1]
    }
    return ans
}

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

给你一个下标从 0 开始的数组 nums ，数组中有 n 个整数，另给你一个整数 k 。

半径为 k 的子数组平均值 是指：nums 中一个以下标 i 为 中心 且 半径 为 k 的子数组中所有元素的平均值，即下标在 i - k 和 i + k 范围（含 i - k 和 i + k）内所有元素的平均值。如果在下标 i 前或后不足 k 个元素，那么 半径为 k 的子数组平均值 是 -1 。

构建并返回一个长度为 n 的数组 avgs ，其中 avgs[i] 是以下标 i 为中心的子数组的 半径为 k 的子数组平均值 。

x 个元素的 平均值 是 x 个元素相加之和除以 x ，此时使用截断式 整数除法 ，即需要去掉结果的小数部分。

例如，四个元素 2、3、1 和 5 的平均值是 (2 + 3 + 1 + 5) / 4 = 11 / 4 = 2.75，截断后得到 2 。

示例 1：

输入：nums = [7,4,3,9,1,8,5,2,6], k = 3

输出：[-1,-1,-1,5,4,4,-1,-1,-1]

解释：

• avg[0]、avg[1] 和 avg[2] 是 -1 ，因为在这几个下标前的元素数量都不足 k 个。
• 中心为下标 3 且半径为 3 的子数组的元素总和是：7 + 4 + 3 + 9 + 1 + 8 + 5 = 37 。 使用截断式 整数除法，avg[3] = 37 / 7 = 5 。
• 中心为下标 4 的子数组，avg[4] = (4 + 3 + 9 + 1 + 8 + 5 + 2) / 7 = 4 。
• 中心为下标 5 的子数组，avg[5] = (3 + 9 + 1 + 8 + 5 + 2 + 6) / 7 = 4 。
• avg[6]、avg[7] 和 avg[8] 是 -1 ，因为在这几个下标后的元素数量都不足 k 个。

示例 2：

输入：nums = [100000], k = 0

输出：[100000]

解释：

• 中心为下标 0 且半径 0 的子数组的元素总和是：100000 。 avg[0] = 100000 / 1 = 100000 。

示例 3：

输入：nums = [8], k = 100000

输出：[-1]

解释：

• avg[0] 是 -1 ，因为在下标 0 前后的元素数量均不足 k 。

提示：

• n == nums.length
• 1 <= n <= 105
• 0 <= nums[i], k <= 105

我的答案:

用一个 cur2 来存储后面的 k 个值, 整体也遵循了 “入-更新-出” 的步骤

func getAverages(nums []int, k int) []int {
	ln := len(nums)
	ans := make([]int, 0, ln)
	cur, cur2 := 0, 0
	for i, n := range nums {
		cur += n
		if i > 0 && i+k < ln {
			cur2 += nums[i+k]
		}
		if i < k || i > ln-k-1 {
			ans = append(ans, -1)
			continue
		}
		ans = append(ans, (cur+cur2)/(2*k+1))
		cur -= nums[i-k]
		if i >= k && i+1 < ln {
			cur2 -= nums[i+1]
		}
	}
	return ans
}

别人的参考答案:

class Solution(object):
    def getAverages(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        mark=0
        n=len(nums)
        avgs=[-1]*n
        for i in range(n):
            mark+=nums[i]
            if i<2*k:
                continue
            avgs[i-k]=mark//(2*k+1) 
            mark-=nums[i-2*k]
        return avgs

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

简单

给你一个长度为 n 下标从 0 开始的字符串 blocks ，blocks[i] 要么是 ‘W’ 要么是 ‘B’ ，表示第 i 块的颜色。字符 ‘W’ 和 ‘B’ 分别表示白色和黑色。

给你一个整数 k ，表示想要 连续 黑色块的数目。

每一次操作中，你可以选择一个白色块将它 涂成 黑色块。

请你返回至少出现 一次 连续 k 个黑色块的 最少 操作次数。

示例 1：

输入：blocks = “WBBWWBBWBW”, k = 7

输出：3

解释：

一种得到 7 个连续黑色块的方法是把第 0 ，3 和 4 个块涂成黑色。

得到 blocks = “BBBBBBBWBW” 。

可以证明无法用少于 3 次操作得到 7 个连续的黑块。

所以我们返回 3 。

示例 2：

输入：blocks = “WBWBBBW”, k = 2

输出：0

解释：

不需要任何操作，因为已经有 2 个连续的黑块。

所以我们返回 0 。

func minimumRecolors(blocks string, k int) int {
    ans := k
    m := map[byte]int{}
    for i, b := range blocks {
        m[byte(b)]++
        if i < k-1 {
            continue
        }
        if m['W'] < ans {
            ans = m['W']
        }
        m[blocks[i-k+1]]--
    }
    return ans
}

1052. 爱生气的书店老板

有一个书店老板，他的书店开了 n 分钟。每分钟都有一些顾客进入这家商店。给定一个长度为 n 的整数数组 customers ，其中 customers[i] 是在第 i 分钟开始时进入商店的顾客数量，所有这些顾客在第 i 分钟结束后离开。

在某些分钟内，书店老板会生气。 如果书店老板在第 i 分钟生气，那么 grumpy[i] = 1，否则 grumpy[i] = 0。

当书店老板生气时，那一分钟的顾客就会不满意，若老板不生气则顾客是满意的。

书店老板知道一个秘密技巧，能抑制自己的情绪，可以让自己连续 minutes 分钟不生气，但却只能使用一次。

请你返回 这一天营业下来，最多有多少客户能够感到满意 。

示例 1：

输入：customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], minutes = 3

输出：16

解释：书店老板在最后 3 分钟保持冷静。

感到满意的最大客户数量 = 1 + 1 + 1 + 1 + 7 + 5 = 16.

示例 2：

输入：customers = [1], grumpy = [0], minutes = 1

输出：1

提示：

• n == customers.length == grumpy.length
• 1 <= minutes <= n <= 2 * 104
• 0 <= customers[i] <= 1000
• grumpy[i] == 0 or 1

我的题解:

func maxSatisfied(customers []int, grumpy []int, minutes int) int {
	if minutes >= len(customers) {
		var total int
		for _, c := range customers {
			total += c
		}
		return total
	}
	var best = 0
	var cur int
	for i := 0; i < len(customers); i++ {
		if i < minutes-1 {
			cur += customers[i]
			continue
		}
		if grumpy[i] == 0 {
			cur += customers[i]
		}
	}
	for i := minutes-1; i < len(customers); i++ {
		if grumpy[i] == 1 {
			cur += customers[i]
		}
		if cur > best {
			best = cur
		}
		if grumpy[i-minutes+1] == 1 {
			cur -= customers[i-minutes+1]
		}
	}
	return best
}

大神题解:

本题可以拆分成两个问题：

1. 老板不生气时的顾客数量之和 s0。这些顾客可以感到满意。
2. 长度为 minutes 的连续子数组中，老板生气时的顾客数量之和 s1 的最大值 maxS1。这些顾客可以感到满意。

最终答案为 s0 + maxS1。

第二个问题可以用定长滑动窗口解决。

例如数组 customers=[3,1,4,1,5,9] 和 minutes=3，假设老板一直在生气：

1. 计算第一个长为 3 的子数组的元素和 3+1+4=8。
2. 计算第二个长为 3 的子数组的元素和，我们可以在第一个子数组元素和的基础上，增加 customers[3]=1，减少 customers[0]=3，得到 8+1−3=6。
3. 计算第三个长为 3 的子数组的元素和，我们可以在第二个子数组元素和的基础上，增加 customers[4]=5，减少 customers[1]=1，得到 6+5−1=10。
4. 计算第四个长为 3 的子数组的元素和，我们可以在第三个子数组元素和的基础上，增加 customers[5]=9，减少 customers[2]=4，得到 10+9−4=15。
5. 最大的长为 3 的子数组和为 15。

func maxSatisfied(customers, grumpy []int, minutes int) int {
    s := [2]int{}
    maxS1 := 0
    for i, c := range customers {
        s[grumpy[i]] += c
        if i < minutes-1 { // 窗口长度不足 minutes
            continue
        }
        maxS1 = max(maxS1, s[1])
        if grumpy[i-minutes+1] > 0 {
            s[1] -= customers[i-minutes+1] // 窗口最左边元素离开窗口
        }
    }
    return s[0] + maxS1
}