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

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

方法一：前缀和

解题思路

通过前缀和计算任意子区间 \([i, i + k - 1]\) 中字母 \(W\) 的数量，\(ans = min([i, i + k - 1].count('W'), i = 0, 1, ...)。\)

代码

class Solution {
public:
    int minimumRecolors(string blocks, int k) {
        int n = blocks.length();
        vector<int> cntW(n + 1); // cntW[i]表示前i个字母中W的个数，i从1开始
        for (int i = 1; i <= n; i ++ ) {
            if (blocks[i - 1] == 'W') cntW[i] = cntW[i - 1] + 1;
            else cntW[i] = cntW[i - 1];
        }
        int ans = INT_MAX;
        for (int i = 1; i + k - 1 <= n; i ++ ) {
            ans = min(ans, cntW[i + k - 1] - cntW[i - 1]);
        }
        return ans;
    }
};

复杂度分析

时间复杂度：\(O(n)\)；
空间复杂度：\(O(n)\)。

方法二：双指针-滑动窗口

解题思路

初始化两个指针\(l = 0，r = k - 1\)，通过两个指针维护大小固定为\(k\)的滑动窗口\([l, r]\)，所有窗口中所含字母\(W\)数量的最小值即为答案。

代码

class Solution {
public:
    int minimumRecolors(string blocks, int k) {
        int l = 0, r = k - 1;
        int cntW = 0; // 表示[l, r]之间字母W的数量
        for (int i = l; i <= r; i ++ )
            if (blocks[i] == 'W') cntW ++ ;
        int ans = INT_MAX;
        while (r < blocks.length()) {
            ans = min(ans, cntW);
            if (blocks[l] == 'W') cntW -- ;
            if (r + 1 < blocks.length() && blocks[r + 1] == 'W') cntW ++ ;
            l ++ ;
            r ++ ;
        }
        return ans;
    }
};

复杂度分析

时间复杂度：\(O(n)\)；
空间复杂度：\(O(1)\)。