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

🟢   🔖  字符串 滑动窗口  🔗 力扣 LeetCode

题目

You are given a 0-indexed string blocks of length n, where blocks[i] is either 'W' or 'B', representing the color of the ith block. The characters 'W' and 'B' denote the colors white and black, respectively.

You are also given an integer k, which is the desired number of consecutive black blocks.

In one operation, you can recolor a white block such that it becomes a black block.

Return _theminimum number of operations needed such that there is at least one occurrence of _k consecutive black blocks.

Example 1:

Input: blocks = "WBBWWBBWBW", k = 7

Output: 3

Explanation:

One way to achieve 7 consecutive black blocks is to recolor the 0th, 3rd, and 4th blocks

so that blocks = "BBBBBBBWBW".

It can be shown that there is no way to achieve 7 consecutive black blocks in less than 3 operations.

Therefore, we return 3.

Example 2:

Input: blocks = "WBWBBBW", k = 2

Output: 0

Explanation:

No changes need to be made, since 2 consecutive black blocks already exist.

Therefore, we return 0.

Constraints:

• n == blocks.length
• 1 <= n <= 100
• blocks[i] is either 'W' or 'B'.
• 1 <= k <= n

题目大意

给你一个长度为 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 。

提示：

• n == blocks.length
• 1 <= n <= 100
• blocks[i] 要么是 'W' ，要么是 'B' 。
• 1 <= k <= n

解题思路

可以利用滑动窗口，使用一个长度为 k 的滑动窗口，统计窗口内 'B' 的数量，窗口中 'B' 的数量越大，说明需要涂色的次数越少。

1. 使用一个变量 curWindowB 统计当前窗口内 'B' 的数量，初始化为 0；
2. 使用一个变量 maxWindowB 记录所有窗口内最大 'B' 数量，初始化为 0；
3. 遍历 blocks，使用一个长度为 k 的滑动窗口，统计窗口内 'B' 的数量；
4. 当窗口长度大于 k 时，移出窗口的左端字符，并更新计数。
5. 通过比较当前窗口的 curWindowB 和 maxWindowB，更新最大值。
6. 遍历结束后，所有窗口内最大 'B' 数量为 maxWindowB，则最少涂色次数为 k - maxWindowB。

复杂度分析

• 时间复杂度：O(n)，其中 n 是 blocks 的长度，遍历一次 blocks。
• 空间复杂度：O(1)，仅使用了常数级别的变量。

代码

/**
 * @param {string} blocks
 * @param {number} k
 * @return {number}
 */
var minimumRecolors = function (blocks, k) {
	let maxWindowB = 0; // 窗口内最多的 'B' 数量
	let curWindowB = 0; // 当前窗口内的 'B' 数量

	for (let i = 0; i < blocks.length; i++) {
		if (blocks[i] === 'B') {
			curWindowB++; // 窗口右端字符是 'B'，计数增加
		}

		if (i >= k && blocks[i - k] === 'B') {
			curWindowB--; // 窗口左端字符移出，计数减少
		}

		if (i >= k - 1) {
			maxWindowB = Math.max(maxWindowB, curWindowB); // 更新最大值
		}
	}

	return k - maxWindowB; // 需要的最少操作数
};

相关题目

题号	标题	题解	标签	难度	力扣
1004	最大连续1的个数 III	[✓]	数组 二分查找 前缀和 1+	🟠	🀄️ 🔗
1423	可获得的最大点数		数组 前缀和 滑动窗口	🟠	🀄️ 🔗
1456	定长子串中元音的最大数目	[✓]	字符串 滑动窗口	🟠	🀄️ 🔗