思维题

lc995

贪心+滑窗

队列维护翻转区间的左端点，遍历数组时判断当前位置是否需要翻转，能翻转则记录左端点并计数，无法翻转则返回-1，最终得到最小翻转次数

class Solution {//贪心地从左到右依次翻转
public:
int minKBitFlips(vector<int>& A, int K) {
int n=A.size(),ans=0;
queue<int> q;
for(int i=0;i<n;++i){
if(!q.empty()&& i-q.front()>=K) q.pop();

//维护与当前位置的距离<=K的翻转位置（左端点）
if((A[i]+q.size())%2==0){ //需要翻转
if(i+K>n) return -1; //无法翻转
q.push(i);
++ans;
}
}
return ans;
}
};

队列动态维护「当前位置被翻转了几次」，快速判断要不要翻转，从而用贪心策略找到最少翻转次数

队列的大小 = 当前位置 i 被翻转的次数

从左到右遍历，遇到 0 就翻转它开头的 K 位，因为如果现在不翻，后面就没机会了