問題描述
給你一個長度為 n 下標從 0 開始的字符串 blocks ，blocks[i] 要么是 W 要么是 B ，表示第 i 塊的顏色。字符 W 和 B 分別表示白色和黑色。
給你一個整數 k ，表示想要 連續(xù) 黑色塊的數目。
每一次操作中，你可以選擇一個白色塊將它 涂成 黑色塊。
請你返回至少出現 一次 連續(xù) k 個黑色塊的 最少 操作次數。
示例
輸入：blocks = "WBBWWBBWBW", k = 7
輸出：3
解釋：
一種得到 7 個連續(xù)黑色塊的方法是把第 0 ，3 和 4 個塊涂成黑色。
得到 blocks = "BBBBBBBWBW" 。
可以證明無法用少于 3 次操作得到 7 個連續(xù)的黑塊。
所以我們返回 3 。
輸入：blocks = "WBWBBBW", k = 2
輸出：0
解釋：
不需要任何操作，因為已經有 2 個連續(xù)的黑塊。
所以我們返回 0 。
解題思路
滑動窗口
建一個長度為k的窗口，先算出當前窗口內的黑塊數；
然后滑動窗口，根據色塊的進出情況，算出窗口內的黑塊數。
在此過程中，根據窗口內黑塊數，得出min。
代碼示例（JAVA）
class Solution {
public int minimumRecolors(String blocks, int k) {
int len = blocks.length();
// 初始化第一個滑動窗口的"當前黑塊數量"
int currentB = 0;
for (int j = 0; j < k; j++) {
if (blocks.charAt(j) == 'B') {
currentB++;
}
}
int min = k - currentB;
for (int i = 1; i <= len - k; i++) {
// 進一個B,走一個W
if (blocks.charAt(k + i - 1) == 'B' && blocks.charAt(i - 1) == 'W') {
currentB++;
min = Math.min(min, k - currentB);
} else if (blocks.charAt(k + i - 1) == 'W' && blocks.charAt(i - 1) == 'B') {
// 進一個W,走一個B
currentB--;
}
}
return min;
}
}
時間復雜度：O(n)
