LeetCode 995 K 连续位的最小翻转次数

本题是一道典型的定长滑动窗口问题，考察了如何处理定长窗口的元素出入窗口，还要注意滑动窗口中暗含的队列式操作的特征，同时本题又考察了差分数组和位运算相关知识，值得深入探讨和研究。

题目描述

原题链接如下： LeetCode 995 K 连续位的最小翻转次数

题目大意

数组 A 有 n 个元素，其可能是 0 或者 1，只允许在数组上进行一种操作：把数组相邻的 K 位进行翻转，即 0 变为 1，而 1 变为 0。假设可以通过若干次翻转使得数组不含有 0 元素，则目标达成不再进行任何操作，求最少的翻转操作次数是多少。另外，如果无法通过任意次翻转 K 位操作得到无 0 数组，则返回 -1。

输入与输出

示例输入为：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

Input 1:
A = [0,1,0]
K = 1

Input 2:
A = [1,1,0]
K = 2

Input 3:
A = [0,0,0,1,0,1,1,0]
K = 3

• A 的长度在 $[1, 30000]$
• K 不大于 A 的长度

对应输出为：

1
2
3
4
5
6
7
8

Output 1:
2

Output 2:
-1

Output 3:
3

解题思路

先考虑基本的翻转策略，我们如果从左往右遍历数组，那么就应该在遇到 0 元素的时候以 0 元素为起始点进行翻转，保证已经遍历过的数组元素性质不变，始终值包含 1 元素。这样，我们实际可能会把 K 长度的滑动窗口内的部分 1 元素便成了 0，就仍需要继续翻转，类似不断的把 0 “向右推”。直到滑动窗口到达数组末尾把所有元素都变为 1 即标志着变化结束，如果必须从某个元素开始进行翻转但窗口结尾超出了数组末尾则这个数组无法进行变化。 这样，暴力解法很好完成，只需要直观地进行翻转操作并计数即可，最后的时间复杂度是 $O(n \cdot K)$，部分语言在数据较大的时候可能会超时无法通过。

队列 + 滑动窗口

观察暴力解法的操作部分，时间复杂度较大的原因在于我们使用了模拟方法进行了翻转操作，方便我们能正确处理多次翻转过的元素。但是，要知道数组元素只有 0 和 1 两种元素，多次翻转的结果有高度规律性：数组元素在奇数次翻转后变为相反元素，偶数次翻转则变为原来元素。那么，我们只要知道一个元素在左边的变化过程中已经被翻转了多少次，就可以确定当前它如果需要被翻转时会变为 1 或者 0，而当前元素的翻转与否又可以累计缓存下来对它之后的元素产生影响。同时，当前元素也不会被所有左侧元素影响，如果左侧元素和它的距离超出了滑动窗口的长度时，那些元素无论如何翻转都不会影响它，同理它也不会影响它右侧的太远的元素。 所以，我们在用空间换时间的时候应该缓存的数据就可以确定：

• 需要缓存翻转操作起点的数组下标，方便计算这个操作影响了那些元素
• 如果部分缓存数据和当前处理元素的下标距离已经超出了 K - 1，那么它们就不再重要，可以删去
• 没有删去的缓存数据的个数就是之前有多少次翻转波及了当前元素
• 当前元素如果需要翻转则也要缓存它的数组下标

显然，我们如果从左往右处理数组元素，那么总是在缓存的一侧加入数组下标，另一侧删除不重要的下标，缓存的数据结构是队列。而队列元素的数量 size 和当前元素数值的关系如下表所示：

所以，只要 size 对 2 除的余数和当前元素相等，即表示当前元素需要翻转。

滑动窗口优化

上文的队列解法其实可以简化，其实大部分时候我们只关注队列的长度和队首元素，检查队首元素是否超出窗口。那么，我们可以在遍历到下标 i 时（即右端点扩张到 i 时），统计窗口内部之前的元素翻转的数量，使用一个变量 flip 记录即可。那么每次移除元素则要去除 A[i - k] 的影响，如果曾经以 A[i - k] 为起点翻转过，则需要 flip--。不难注意到其实 flip 的值就是队列解法中队列的长度。但是，没有队列我们如何记录曾经的翻转起点呢？ 如果，数组 A 可以修改，其实我们可以利用 A 本身记录这个信息，因为 A 的元素只有 0 和 1，每当 A[i] 是翻转的起点只需把它按位反转即可。在右端点扩张到 i 时，如果 A[i - k] 小于 0 则相当于原来的队列队首元素超出了窗口范围。 最后，既然队列长度（即 flip 的值）对于当前元素是否需要翻转的影响，只在于它的奇偶性，说明我们只需要它的二进制数字的最后一位比特位。因此，无需使用加减法，flip++ 和 flip-- 都变成 flip = flip xor 1 即可。 如果，题目需要复原数组 A，则可以在遍历一次数组，把所有小于 0 的元素按位反转即可。

注意：

• 定长滑动窗口实质上就是只收缩 1 个元素的不定长滑动窗口，不定长窗口常常求窗口长度的最值，而定长窗口则求窗口内元素的各种统计值
• 如果对操作和相关概念熟悉，定长的滑动窗口题目可以直接使用类似的模板代码，无需借助队列做中介，但仍要注意这种情况下暗含的队列性质。

差分数组

本题需要反复对数组的子数组进行同样的操作，而我们关心的又只是操作数，所以我们可以引入差分数组记录区间内的变化数量。原先数组 arr 的差分数组是如下定义的：

$$ diff[i]= \begin{cases} arr[0]& \text{i = 0}\\ arr[i] - arr[i-1]& \text{i > 0} \end{cases} $$

此时的 arr[i] 就是数组 A 以 0 开始以下标 i 为结尾的子数组排除 0 元素需要的操作数。那么，我们可以沿用暴力模拟的思路，但是每次翻转无需 K 次翻转，只需要对滑动窗口上差分数组的右端进行操作，把 $O(K)$ 时间复杂度的操作变成了 $O(1)$ 时间复杂度。

• 本题差分数组不是数组 A 的差分，而是虚拟的操作数数组的差分，所以初始项目为 0。
• 原题无需还原数组，而且可以借助一个变量累加差分数组的和，那么就无需严格遵照定义对差分数组的左侧端点进行相应操作，毕竟左侧端点的值对结果无影响。

最后，类似滑动数组优化解法，累加和最后对是否翻转的影响仅仅在于它除以 2 的余数，那么我们无需使用加法，使用异或即可，对结果无影响。

代码

滑动窗口队列解法：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    fun minKBitFlips(arr: IntArray, k: Int): Int {
        var re = 0
        val queue = ArrayDeque<Int>()
        for (i in arr.indices) {
            if (queue.isNotEmpty() && queue.first() + k == i) queue.removeFirst()
            if (queue.size % 2 == arr[i]) {
                if (i + k > arr.size) return -1
                re++
                queue.addLast(i)
            }
        }
        return re
    }
}

滑动窗口优化解法：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
    fun minKBitFlips(A: IntArray, K: Int): Int {
        var re = 0
        var flip = 0
        for (i in A.indices) {
            if (i >= K && A[i - K] < 0) flip = flip xor 1
            if (flip == A[i]) {
                if (i + K > A.size) return -1
                flip = flip xor 1
                A[i] = A[i].inv()
                re++
            }
        }
        return re
    }
}

差分数组解法：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution {
    fun minKBitFlips(A: IntArray, K: Int): Int {
        val diff = IntArray(A.size + 1)
        var re = 0
        var flip = 0
        for (i in A.indices) {
            flip = flip xor diff[i]
            if (flip == A[i]) {
                if (i + K > A.size) return -1
                flip = flip xor 1
                diff[i + K] = diff[i + K] xor 1
                re++
            }
        }
        return re
    }
}