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

题目描述

给定一个由字符 'W'（白色块）和 'B'（黑色块）组成的字符串 blocks，以及一个整数 k。我们需要通过最少的操作次数，使得字符串中存在至少一个长度为 k 的连续黑色块。每次操作可以将一个白色块涂成黑色块。

输入输出示例

输入：

blocks = "WBBWWBBWBW", k = 7

输出：

3

解释：选择从索引 0 到 6 的子字符串，其中包含 3 个白色块。将这些白色块涂黑后，即可得到连续 7 个黑色块。

解题思路分析

1. 暴力法的局限性

最直观的思路是遍历所有长度为 k 的子字符串，统计每个子串中白色块的数量，并取最小值。这种方法的时间复杂度为 O(nk)，当 n 较大时（如 n=1e5），会导致超时。

示例分析：
对于字符串 "WBBWWBBWBW" 和 k=7，暴力法需要检查以下子串：

• "WBBWWBB" → 3 个 W
• "BBWWBBW" → 2 个 W
• "BWWBBWB" → 3 个 W
• "WWBBWBW" → 3 个 W
• "WBBWBWW" → 3 个 W
• "BBWBWWB" → 2 个 W
• "BWBWWBW" → 3 个 W
• "WBWWBWB" → 3 个 W
• "BWWBWBW" → 3 个 W

虽然暴力法可以得到正确结果，但效率较低。

2. 滑动窗口算法的优化

滑动窗口算法通过维护一个大小为 k 的窗口，动态调整窗口的位置，避免重复计算。具体步骤如下：

1. 初始化窗口：计算前 k 个字符中白色块的数量。
2. 滑动窗口：每次向右移动一位，移除左边界字符，添加右边界字符，更新白色块数量。
3. 记录最小值：在每次滑动后，更新最小操作次数。

时间复杂度：O (n)，只需遍历字符串一次。
空间复杂度：O (1)，仅使用常数额外空间。

代码实现（Java）

class Solution {
    public int minimumRecolors(String blocks, int k) {
        int n = blocks.length();
        if (n < k) return n; // 特殊情况处理
        
        int currentW = 0;
        // 初始化第一个窗口的白色块数量
        for (int i = 0; i < k; i++) {
            if (blocks.charAt(i) == 'W') {
                currentW++;
            }
        }
        int minOps = currentW; // 初始最小值
        
        // 滑动窗口遍历剩余位置
        for (int i = 1; i <= n - k; i++) {
            // 移除左边界字符
            if (blocks.charAt(i - 1) == 'W') {
                currentW--;
            }
            // 添加右边界字符
            int right = i + k - 1;
            if (blocks.charAt(right) == 'W') {
                currentW++;
            }
            // 更新最小值
            minOps = Math.min(minOps, currentW);
        }
        return minOps;
    }
}

代码逐行解析

1. 特殊情况处理

if (n < k) return n;

当字符串长度小于 k 时，无法形成长度为 k 的子串，因此需要将整个字符串涂黑，操作次数为 n。

2. 初始化窗口

int currentW = 0;
for (int i = 0; i < k; i++) {
    if (blocks.charAt(i) == 'W') {
        currentW++;
    }
}

遍历前 k 个字符，统计白色块的数量 currentW。

3. 滑动窗口遍历

for (int i = 1; i <= n - k; i++) {
    // 移除左边界字符
    if (blocks.charAt(i - 1) == 'W') {
        currentW--;
    }
    // 添加右边界字符
    int right = i + k - 1;
    if (blocks.charAt(right) == 'W') {
        currentW++;
    }
    // 更新最小值
    minOps = Math.min(minOps, currentW);
}

• 窗口移动：i 表示新窗口的起始位置。
• 移除左边界：如果原左边界字符是 'W'，则减少 currentW。
• 添加右边界：计算新右边界的位置 right = i + k - 1，如果该字符是 'W'，则增加 currentW。
• 更新最小值：每次滑动后，比较当前窗口的 currentW 与 minOps，取较小值。

复杂度分析

1. 时间复杂度

• 初始化窗口：O (k)
• 滑动窗口遍历：O (n - k)
• 总时间复杂度：O (n)

2. 空间复杂度

• 仅使用了 currentW、minOps 等常数变量，空间复杂度为 O (1)。

常见问题解答

Q1：为什么滑动窗口的右边界是 i + k - 1？

当窗口起始位置为 i 时，窗口的结束位置为 i + k - 1。例如：

• i=0 → 窗口为 0~k-1
• i=1 → 窗口为 1~k

Q2：为什么循环条件是 i <= n - k？

当 i 超过 n - k 时，窗口无法包含 k 个字符。例如：

• n=10, k=7 → 最大 i 为 3（窗口为 3~9）

Q3：如何处理全是黑色块的情况？

当 currentW 初始化为 0 时，直接返回 0。

总结

滑动窗口算法是解决连续子数组 / 子字符串问题的高效方法。通过动态维护窗口的左右边界，避免了重复计算，时间复杂度降低到 O (n)。在本题中，我们利用滑动窗口快速找到最优解，显著提升了算法效率。掌握这一技巧对于应对面试和实际开发中的类似问题非常关键。

如果您有任何疑问或建议，欢迎在评论区交流！ 🚀