# 0995. K 连续位的最小翻转次数

### 题目地址(995. K 连续位的最小翻转次数)

<https://leetcode-cn.com/problems/minimum-number-of-k-consecutive-bit-flips/>

### 题目描述

```
在仅包含 0 和 1 的数组 A 中，一次 K 位翻转包括选择一个长度为 K 的（连续）子数组，同时将子数组中的每个 0 更改为 1，而每个 1 更改为 0。

返回所需的 K 位翻转的最小次数，以便数组没有值为 0 的元素。如果不可能，返回 -1。

 

示例 1：

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


示例 2：

输入：A = [1,1,0], K = 2
输出：-1
解释：无论我们怎样翻转大小为 2 的子数组，我们都不能使数组变为 [1,1,1]。


示例 3：

输入：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
```

### 前置知识

* 连续子数组优化

### 公司

* 暂无

### 暴力解

#### 思路

首先考虑暴力的解法。暴力的思路可以是从左到右遍历数组，如果碰到一个 0，我们以其为左端进行翻转。翻转的长度自然是以其开始长度为 K 的子数组了。由于是**以其为左端进行翻转**，因此如果遇到一个 0 ，我们必须执行翻转，否则就无法得到全 1 数组。由于翻转的顺序不影响最终结果，即如果最终答案是翻转以 i, j , k 为起点的子数组，那么先翻转谁后翻转谁都是一样的。因此采用从左往右遍历的方式是可以的。

概括一下：暴力的思路可以是从左到右遍历数组，如果碰到一个 0，我们以其为左端进行翻转，并修改当前位置开始的长度为 k 的子数组，同时计数器 + 1，最终如果数组不全为 0 则返回 -1 ，否则返回计数器的值。

#### 代码

* 语言支持：Python3

Python3 Code:

```py
class Solution:
    def minKBitFlips(self, A, K):
        N = len(A)
        ans = 0
        for i in range(N - K + 1):
            if A[i] == 1:
                continue
            for j in range(K):
                A[i + j] ^= 1
            ans += 1
        for i in range(N):
            if A[i] == 0:
                return -1
        return ans
```

**复杂度分析**

令 n 为数组长度。

* 时间复杂度：$O(n \* k)$
* 空间复杂度：$O(1)$

### 连续子数组优化

#### 思路

对于这种连续子数组的题目。一般优化思路就那么几种。我们来枚举一下：

* [前缀和 & 差分数组](/leetcode-solution/selected/atmostk.md)
* [滑动窗口](/leetcode-solution/thinkings/slide-window.md)
* 双端队列。比如 1696. 跳跃游戏 VI 和 239. 滑动窗口最大值 就是这种思路。

这三种技巧我都写过文章，如果不了解可以先看下。

对于这道题来说，我们可使用差分数组或者双端队列来优化。不管采用哪种，基本思路都差不多，你也可以对比下方代码看一下他们思路的一致性。 简单来说，他们的思路差不多，差别只是解决问题的使用的数据结构不同，因此 api 不同罢了。因此我并没有将二者作为两个解法。

对于差分数组来说，上面暴力解法内层有一个次数为 k 的循环。而如果使用差分数组只修改端点的值，就可轻松将时间复杂度优化到 $O(n)$。

对于双端队列来说，如果当前位置需要翻转，那么就将其入队。那如何判断当前位置的数字是多少呢？（可能由于前面数字的翻转，当前位置**被**翻转了若干次，可能不是以前的数字了）。由于被翻转偶数次等于没有翻转，被翻转奇数次效果一样，因此只需要记录被翻转次数的奇偶性即可。而这其实就是队列长度的奇偶性。因为**此时队列的长度就是当前数字被翻转的次数**。当然这要求你将长度已经大于 k 的从队列中移除。

#### 关键点

* 连续子数组优化技巧

#### 代码

* 语言支持：Python3

Python3 Code:

差分数组：

```py

class Solution:
    def minKBitFlips(self, A: List[int], K: int) -> int:
        n = len(A)
        diff = [0] * (n + 1)
        ans, cur = 0, 0
        for i in range(n):
            cur += diff[i]
            if cur % 2 == A[i]:
                if i + K > n:
                    return -1
                ans += 1
                cur += 1
                diff[i + K] -= 1
        return ans

```

**复杂度分析**

令 n 为数组长度。

* 时间复杂度：$O(n)$
* 空间复杂度：$O(n)$

双端队列：

```py
class Solution:
    def minKBitFlips(self, A, K):
        N = len(A)
        q = collections.deque()
        ans = 0
        for i in range(N):
            if q and i >= q[0] + K:
                q.popleft()
            if len(q) % 2 == A[i]:
                if i + K > N:
                    return -1
                q.append(i)
                ans += 1
        return ans
```

**复杂度分析**

令 n 为数组长度。

* 时间复杂度：$O(n)$
* 空间复杂度：$O(k)$

### 空间复杂度为 O(1) 的算法

#### 思路

不管是使用差分数组和还是双端队列，其实都没有必要使用额外的数据结构，而是使用原来的数组 A，也就是**原地修改**。

比如，我们可以只记录双端队列的长度，要判断一个数字是否在队列里，只需要将其映射到题目数据范围内的另外一个数字即可。由于题目数据范围是 \[0,1] 因此我们可以将其映射到 2。

#### 关键点

* 原地修改

#### 代码

* 语言支持：Python3

Python3 Code:

```py

class Solution:
    def minKBitFlips(self, A, K):
        flips = ans = 0
        for i in range(len(A)):
            if i >= K and A[i - K] - 2 == 0:
                flips -= 1
            if (flips % 2) == A[i]:
                if i + K > len(A):
                    return -1
                A[i] = 2
                flips += 1
                ans += 1
        return ans

```

**复杂度分析**

令 n 为数组长度。

* 时间复杂度：$O(n)$
* 空间复杂度：$O(1)$

> 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。

力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦\~

以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：<https://github.com/azl397985856/leetcode> 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。

![](https://p.ipic.vip/3992tg.jpg)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/hard/995.minimum-number-of-k-consecutive-bit-flips.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.