LeetCode 2379. 得到 K 個黑塊的最少塗色次數（滑動視窗圖解）

2379. 得到 K 個黑塊的最少塗色次數

題目描述

給你一個長度為 n、下標從 0 開始的字串 blocks，blocks[i] 要么是 'W'，要么是 'B'，表示第 i 塊的顏色：'W' 為白色，'B' 為黑色。

再給你一個整數 k，表示想要連續黑色塊的數目。

每一次操作，你可以選擇一個白色塊把它塗成黑色。請回傳至少出現一次連續 k 個黑色塊的最少操作次數。

範例 1

輸入：blocks = "WBBWWBBWBW", k = 7
輸出：3
解釋：把第 0、3、4 個塊塗成黑色，得到 "BBBBBBBWBW"，
可以證明無法用少於 3 次操作得到 7 個連續黑塊。

範例 2

輸入：blocks = "WBWBBBW", k = 2
輸出：0
解釋：已經有 2 個連續黑塊，不需要任何操作。

限制

• n == blocks.length
• 1 <= n <= 100
• blocks[i] 為 'W' 或 'B'
• 1 <= k <= n

本文題解思路與程式碼整理自 LeetCode 題解作者「灵茶山艾府」，影片講解。圖解為自行補充。

前置知識：滑動視窗

視窗指的是陣列／字串中由起訖索引定義的一段連續元素，即閉區間 [i, j]。把視窗向右滑動 1 格，就變成 [i+1, j+1]：視窗少了元素 i，多了元素 j+1。

思路

最後要的是「連續 k 格全黑」，而每次操作只能把一個 W 變成 B，所以：

任選一段長度為 k 的區間，把裡面的 W 全部塗黑，成本就是這段區間內 W 的數量。

因此問題變成：長度固定為 k 的滑動視窗，求視窗內 W 數量的最小值。

1. 初始化：數出前 k 格內 W 的個數，記為 cntW，同時令 ans = cntW。
2. 視窗向右滑動一格：新進入的格子是 W 則 cntW + 1；剛離開的格子是 W 則 cntW - 1。
3. 每次滑動後 ans = min(ans, cntW)。
4. 視窗到達最右邊時，ans 就是答案。

圖解（可互動）

用範例 1 blocks = "WBBWWBBWBW"、k = 7 一步一步看視窗怎麼滑動。按「下一步」往右滑，觀察 cntW（視窗內 W 數量）與 ans（目前最小值）怎麼變化。

上一步 下一步 重置

blocks = "WBBWWBBWBW"，k = 7

B（算 0） W（算 1） 視窗內 入 = 新進入 出 = 剛離開

視窗內 W 數量 cntW0

目前最小值 ans0

解法一：直接判斷 W（較好懂）

與下方解法二思路相同，只是不用 ASCII 技巧，直接用 if 判斷字元是不是 'W'，可讀性較好。

class Solution {
    public int minimumRecolors(String blocks, int k) {
        int cntW = 0;

        // 1. 建立第一個長度為 k 的視窗，計算初始的 'W' 數量
        for (int i = 0; i < k; i++) {
            if (blocks.charAt(i) == 'W') {
                cntW++;
            }
        }

        int ans = cntW;

        // 2. 視窗開始往右滑動：加入右邊 blocks[i]，移出左邊 blocks[i - k]
        for (int i = k; i < blocks.length(); i++) {
            if (blocks.charAt(i) == 'W') {
                cntW++; // 新進入視窗的是 W，計數加 1
            }
            if (blocks.charAt(i - k) == 'W') {
                cntW--; // 移出視窗的是 W，計數減 1
            }
            ans = Math.min(ans, cntW);
        }

        return ans;
    }
}

解法二：位元運算（灵茶山艾府）

class Solution {
    public int minimumRecolors(String blocks, int k) {
        char[] s = blocks.toCharArray();
        int cntW = 0;
        // 先數出前 k 格內 W 的數量，作為初始視窗
        for (int i = 0; i < k; i++) {
            cntW += s[i] & 1;
        }
        int ans = cntW;
        // 視窗右移：右端進來一格，左端離開一格
        for (int i = k; i < s.length; i++) {
            cntW += (s[i] & 1) - (s[i - k] & 1);
            ans = Math.min(ans, cntW);
        }
        return ans;
    }
}

解法二的小技巧：s[i] & 1

'W' 的 ASCII 是 87（二進位最低位為 1），'B' 是 66（最低位為 0），所以 s[i] & 1 剛好把 W 當成 1、B 當成 0，不必寫 if-else。

字元 W、B 可視為隨機出現，用 if-else 會讓 CPU 的分支預測有約 50% 失敗率，回滾指令要多花 CPU 週期；改成位元運算可以去掉分支。不過這種寫法會降低可讀性，本題資料範圍小看不出差別，業務程式碼中建議還是寫清楚的版本。

複雜度分析

• 時間複雜度：O(n)，其中 n 為 blocks 的長度，每個字元最多進出視窗各一次。
• 空間複雜度：O(1)，只用到幾個額外變數（toCharArray 的陣列不計入的話）。