原题地址（困难）

方法1—模拟

思路

从左到右，遇0则变，然而超时了。

代码

略

时空复杂度

时间 空间

方法2—滑动窗口

思路

参考了以下题解。

需要注意：某位置i处的元素需不需要翻转，取决于该元素的值以及前面 **[i-k+1, i)** 区间内的元素的翻转次数
比如说数组 A=[0,1,0,1,1], k=3 ，第二个元素1需要翻转，因为它是1，且前面 **[i-k+1, i)** 区间内的元素共翻转了1次，所以它也需要翻转。

总结来说，如果 A[i] 是1，则翻转偶数次满足题意；如果 A[i] 是0，则共翻转奇数次满足题意。
即我们如果设前面指定区间内的元素共翻转了 n 次，则当 n + A[i] % 2 == 1 时，则该元素不再需要翻转，已经是1了，否则该元素需要再翻转一次。

所以我们可以维护 一个队列 ，用来模拟滑动窗口，从左到右遍历数组，到索引 i 的元素时，队列中存储的是：

• 前面k-1个元素中（即区间**[i-k+1, i)** ），以哪些位置起始的子区间进行了翻转，就把这个起始位置push到队列中。

这样，队列的长度就代表了上述的 n 。

而某元素索引是否push到队列中，就可以用n + A[i] % 2来判断。

哦，对了，还要定期清理掉不在区间**[i-k+1, i)** 内的索引。

代码

class Solution {
public:
    int minKBitFlips(vector<int>& A, int K) {
        queue<int> q;
        int ans = 0;
        for(int i=0; i<A.size(); i++) {
            if(!q.empty() && i >= q.front() + K)
                q.pop();
            if((q.size() + A[i]) % 2 == 0) {
                if(i + K > A.size())   
                    return -1;
                // 需翻转
                ans++;
                q.push(i);
            }
        }
        return ans;
    }
};

时空复杂度

时间 空间