题目描述

在数组 A 中仅包含 0 和 1，一个 K 位的翻转 由如下方式组成，选择一个（连续）的长度为 K 的子数组，同时翻转子数组中的每一个 0 为 1，每一个 1 为 0。

返回最少的 K 位翻转 的操作次数，使得数组中不存在 0。如果这不可能，则返回 -1。

样例

输入：A = [0,1,0], K = 1
输出：2
解释：翻转 A[0]，然后翻转 A[2]。

输入：A = [1,1,0], K = 2
输出：-1
解释：无论我们怎么翻转长度为 2 的子数组，我们不可能使数组变成 [1,1,1]。

输入：A = [0,0,0,1,0,1,1,0], K = 3
输出：3
解释：
翻转 A[0],A[1],A[2]: A 变为 [1,1,1,1,0,1,1,0]
翻转 A[4],A[5],A[6]: A 变为 [1,1,1,1,1,0,0,0]
翻转 A[5],A[6],A[7]: A 变为 [1,1,1,1,1,1,1,1]

注意

• 1 <= A.length <= 30000
• 1 <= K <= A.length

算法

(贪心，差分思想) $O(n)$

1. 显然我们需要一个策略来翻转数组。
2. 这里不加证明地给出最优的策略，考虑从数组开头开始检查，如果遇到了 0，则累计答案并翻转当前位置及当前位置之后的 K 个元素，使得当前位置变为 1，然后继续检查下一个位置。如果遇到了 1 则不进行任何操作。如果在最后不足 K 个位置的时候遇到了 0，则返回 -1。
3. 但这样操作时间复杂度是 $O(nK)$ 的，需要进行优化。我们发现，每个位置的状态和操作次数的奇偶有关系，而每次我们又是操作连续的位置，则考虑差分的思想。
4. 额外建立一个数组 B，初始值都为 0，额外维护一个当前的和 cur。如果 cur + A[i] + B[i] 为 0，则需要进行翻转，则累计答案的同时， cur = cur + 1 + B[i]，且 B[i + K] = -1；否则，只需要 cur = cur + B[i]。

时间复杂度

• 优化后的策略每个位置仅进行常数时间的操作，故时间复杂度为 $O(n)$。

空间复杂度

• 由于使用了额外数组，空间复杂度为 $O(n)$。

C++ 代码

class Solution {
public:
    int minKBitFlips(vector<int>& A, int K) {
        int n = A.size();
        int cur = 0, ans = 0;
        vector<int> B(n, 0);
        for (int i = 0; i < n; i++)
            if ((A[i] + B[i] + cur) % 2 == 0) {
                ans++;
                if (i + K < n)
                    B[i + K] = -1;
                else if (i + K > n)
                    return -1;
                cur += B[i] + 1;
            }
            else {
                cur += B[i];
            }
        return ans;
    }
};