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

题意

给你一个长度为 n、只包含 B 和 W 的字符串 blocks，其中 B 表示黑色块，W 表示白色块。

一次操作可以把一个白色块变成黑色块。返回让某个长度为 k 的连续区间全部变成黑色所需的最少操作次数。

题目链接：2379. 得到 K 个黑块的最少涂色次数

思路

要让长度为 k 的连续区间全部变成黑色，只需要把这个区间里的所有白色块 W 涂成黑色。

所以问题等价于：

在所有长度为 k 的窗口中，找到白色块数量的最小值。

维护固定大小为 k 的滑动窗口：

1. 进入窗口：遍历 blocks，如果当前字符是 W，就让 countW++。
2. 窗口未成形：当左端点 left = i - k + 1 小于 0 时，说明窗口长度还不到 k，先跳过。
3. 更新答案：窗口长度达到 k 后，用当前窗口中的白块数量更新 minW。
4. 移出窗口：把窗口最左侧字符移出；如果它是 W，就让 countW--。

最终 minW 就是最少需要涂色的次数。

代码

function minimumRecolors(blocks: string, k: number): number {
    let minW = Infinity;
    let countW = 0;
    for (let i = 0; i < blocks.length; i++) {
        // 入
        if (blocks[i] === 'W') {
            countW++;
        }
 
        let left = i - k + 1;
        if (left < 0) {
            continue;
        }
 
        // 更新
        minW = Math.min(countW, minW);
 
        // 出
        if (blocks[left] === 'W') {
            countW--;
        }
    }
    return minW;
};

复杂度

• 时间复杂度：$O(n)$，每个字符最多进入和离开窗口一次。
• 空间复杂度：$O(1)$，只维护白块数量和答案。