666 字
3 分钟
2379. 得到 K 个黑块的最少涂色次数
2379. 得到 K 个黑块的最少涂色次数
题目描述
给你一个长度为 n 的字符串 blocks，其中 blocks[i] 是 'W' 或 'B'，表示第 i 块的颜色。字符 'W' 表示白色，'B' 表示黑色。
给你一个整数 k，表示想要连续 k 个黑块。每次操作可以将一个白块涂成黑块。
返回最少操作次数。
示例 1：
输入：blocks = "WBBWWBBWBW", k = 7输出：3示例 2：
输入：blocks = "WBWBBBW", k = 2输出：0提示：
n == blocks.length1 <= k <= n <= 100
解法思路
定长滑动窗口。目标是得到连续 k 个黑块。涂色只能把白变黑，所以：
想让某一段连续 k 个位置全变成黑，就必须把这段里所有
'W'涂黑。答案 = 所有长度为 k 的子段中，'W'个数的最小值。
（等价地也可以统计窗口内 'B' 个数的最大值，答案 = k - max_B。）
这样就把修改型问题翻译成了纯粹的滑窗统计问题，沿用 入-更新-出 三步，只需维护窗口内 'W' 的计数：
- 入：右端点
blocks[i]进窗口，若是'W'则cur += 1；窗口不足 k 时继续。 - 更新：窗口长度为 k，用
cur更新最小值ans。 - 出：左端点
blocks[i-k+1]出窗口，若是'W'则cur -= 1。
细节：答案本质上是一个「不停变小」的值，ans 初值设为第一个窗口的 'W' 数即可；若某个窗口已不含 'W'（即已有连续 k 个黑块），答案是 0 并可提前结束。
逐步举例（blocks = "WBBWWBBWBW", k = 7）。枚举所有长 7 窗口并统计其中 'W' 的个数：
| 窗口（下标） | 内容 | W 个数 |
|---|---|---|
| [0..6] | W B B W W B B | 3 |
| [1..7] | B B W W B B W | 3 |
| [2..8] | B W W B B W B | 3 |
| [3..9] | W W B B W B W | 4 |
'W' 最少是 3，所以最少涂色 3 次即可得到连续 7 个黑块，与预期一致。我们把”修改”问题转成了”统计每个窗口内 W 的最小值”问题。
思路与写法参考灵茶山艾府《【模板】定长滑动窗口》及 2379 对应题解；关于二进制低位取值的
&1优化见灵神题解（可读性优先时直接比较字符即可）。
复杂度分析
- 时间复杂度：O(n)，每个字符进出窗口各一次。
- 空间复杂度：O(1)。
代码实现
class Solution: def minimumRecolors(self, blocks: str, k: int) -> int: cur = blocks[:k].count("W") ans = cur for i in range(k, len(blocks)): cur += (blocks[i] == "W") - (blocks[i - k] == "W") if cur < ans: ans = cur return ansimport unittest
class TestMinimumRecolors(unittest.TestCase): def setUp(self): self.solution = Solution()
def test_example1(self): self.assertEqual(self.solution.minimumRecolors("WBBWWBBWBW", 7), 3)
def test_example2(self): self.assertEqual(self.solution.minimumRecolors("WBWBBBW", 2), 0)
def test_all_white(self): self.assertEqual(self.solution.minimumRecolors("WWWWW", 3), 3)
if __name__ == "__main__": unittest.main() 2379. 得到 K 个黑块的最少涂色次数
https://h1s97x.github.io/posts/coding/coding-2379-min-recolors/ 
