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

2023-04-21 HGNULB 约 11 分钟

文章信息 6 个分类 6 个标签

分类

题目描述

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

题意分析

给一个 0/1 数组 nums 和一个整数 k。一次操作是选一个长度恰好为 k 的连续子数组，把里面所有位取反（0 变 1、1 变 0）。求把整个数组变成全 1 的最少操作次数；做不到就返回 -1。

先厘清三条性质，它们决定了整道题的形态。

第一，同一个起点翻转两次等于没翻，所以每个起点最多翻一次，方案本质上是「选择一个起点集合」。第二，翻转的顺序不影响最终结果——每个位置最终的值只取决于覆盖它的翻转次数的奇偶性，这把「操作序列」降维成了「计数问题」。第三，长度必须恰好 k，不能更短，所以起点 i 必须满足 i + k <= n，末尾 k - 1 个位置无法作为起点。

约束里 n 最大到 $10^5$，k <= n。这个规模排除了 $O(nk)$ 的朴素模拟（最坏 $10^{10}$），要求 $O(n)$ 或 $O(n \log n)$。而「每个位置只关心被覆盖次数的奇偶」正好是差分数组的用武之地——差分能把「区间加」摊成两次单点修改，配合前缀累加在 $O(1)$ 内得到当前覆盖次数。

边界方面：k = 1 时每个 0 单独翻一次，必然有解；k = n 时只有一个可选起点，要么全 0（翻一次）要么全 1（翻零次），否则无解；数组本身全 1 时答案是 0。返回 -1 的判定必须精确——不是「最后还有 0」就完事，而是在扫描过程中发现「当前位置需要翻转但已经没有足够长度」时立刻断言无解。

解法：贪心 + 差分维护翻转奇偶

核心思路

暴力做法是从左到右扫，遇到 0 就把 [i, i+k-1] 整段翻转，逐位改数组。这个策略本身是对的，但每次翻转要动 k 个元素，最坏 $O(nk)$，n 与 k 都到 $10^5$ 时超时。

先说清楚为什么贪心策略正确。从左往右看第一个位置 i = 0：能覆盖它的翻转起点只有 0 这一个（起点必须 <= 0 且非负）。所以如果 nums[0] 是 0，那么「以 0 为起点翻一次」是唯一的选择，没有任何自由度；如果 nums[0] 是 1，那就绝不能翻（翻了就变 0，且再也无法补救）。处理完位置 0 之后，它就固定了，问题变成了对剩余部分的同型子问题。归纳下去，就得到：从左到右扫描，当前位置（考虑此前所有翻转的影响后）若为 0，就必须以它为起点翻一次。每一步都无选择，因此得到的就是最优解，而且如果这个策略失败，就说明无解。

再解决效率。既然只关心「当前位置被覆盖了奇数次还是偶数次」，就不必真的去改数组。维护一个变量 flip 表示当前位置累计被翻转次数的奇偶性（0 表示偶数次即没变，1 表示奇数次即已取反），那么位置 i 的实际值就是 nums[i] ^ flip。

问题只剩下：怎么让 flip 在扫描时自动加上「新开始的翻转」并减去「已经结束的翻转」。这正是差分：以 i 为起点的翻转影响区间是 [i, i+k-1]，它在 i 处生效、在 i+k 处失效。于是开一个数组 diff，在决定翻转时执行 diff[i+k] ^= 1 登记「到 i+k 就该撤销」；扫描到每个位置先做 flip ^= diff[i]，把该失效的影响剔除掉。

用异或而不是加减，是因为我们只关心奇偶性，异或天然就是模 2 加法，还免去了取模。

维持的不变量是：在处理位置 i 的循环体开头（执行完 flip ^= diff[i] 之后），flip 恰好等于「所有起点在 [i-k+1, i] 范围内、已经决定执行的翻转次数」的奇偶性，也就是位置 i 当前被覆盖的次数的奇偶。因此 nums[i] ^ flip 就是位置 i 此刻的真实值。

无解的判定就落在贪心的唯一性上：若位置 i 当前是 0，必须以 i 为起点翻转，但 i + k > n 说明放不下长度为 k 的窗口，而其他任何起点都无法再影响到 i（更靠左的起点已经全部决定完毕，更靠右的起点覆盖不到 i），所以直接返回 -1。

解题步骤

准备 diff 数组（长度 n + 1）、flip = 0、answer = 0。为什么长度是 n + 1：登记失效位置时会写到 i + k，而 i + k 最大可以等于 n，多留一格避免越界；下标 n 这一格写了也不会被读到，纯粹是哨兵。

从左到右遍历每个位置 i：贪心必须按这个方向，因为「唯一起点」的论证依赖于左边的位置已经全部定案。

先更新奇偶性：flip ^= diff[i]。为什么放在循环体第一行：diff[i] 记录的是「在 i 处失效」的翻转，必须先把它们剔除，flip 才能准确反映位置 i 的覆盖情况；放在后面会让已经结束的翻转多影响一个位置。

判断当前位置的真实值：nums[i] ^ flip。为什么用异或：翻转偶数次等于没翻（异或 0），奇数次等于取反（异或 1），异或正好表达这个语义且是常数时间。

若真实值为 0，必须翻转：先检查 i + k > n，成立就返回 -1（放不下窗口且无人能救）。为什么条件是 i + k > n 而不是 i + k >= n：起点 i 对应的区间是 [i, i+k-1]，只要 i + k - 1 <= n - 1 即 i + k <= n 就合法。

执行翻转的三件事：answer++ 计数；flip ^= 1 让本次翻转立刻对当前位置及后续位置生效；diff[i+k] ^= 1 登记它在 i + k 处失效。三者缺一不可——漏掉 flip ^= 1，当前位置的 0 就没被真正修正；漏掉 diff[i+k] ^= 1，这次翻转会一直影响到数组末尾。

若真实值为 1 则什么都不做：翻转它只会变成 0，且后续无法补救，贪心的唯一性在这里同样成立。

循环结束返回 answer：能走完说明每个位置都被修正为 1。为什么不需要最后再检查一遍数组：扫描过程中每个位置都在它自己那一轮被确认为 1（要么本来就是，要么被强制翻成），不存在漏网之鱼。

以 nums = [0,1,0]、k = 1 走一遍（预期答案 2）。diff 长度 4，flip = 0，answer = 0。
i = 0：flip ^= diff[0] = 0，仍是 0。真实值 0 ^ 0 = 0，需翻转。0 + 1 = 1 <= 3，合法。answer = 1，flip = 1，diff[1] ^= 1。
i = 1：flip ^= diff[1] = 1，flip 回到 0（上一次翻转只覆盖长度 1，到这里正好失效）。真实值 1 ^ 0 = 1，无需翻转。
i = 2：flip ^= diff[2] = 0，仍是 0。真实值 0 ^ 0 = 0，需翻转。2 + 1 = 3 <= 3，合法。answer = 2，flip = 1，diff[3] ^= 1。
返回 2，正确。

再看 nums = [0,0,0,1,0,1,1,0]、k = 3（预期答案 3）。
i = 0：flip = 0，真实值 0，翻转。answer = 1，flip = 1，diff[3] ^= 1。此时逻辑上 [0,1,2] 已被翻成 1,1,1。
i = 1：diff[1] = 0，flip 仍是 1。真实值 0 ^ 1 = 1，跳过。
i = 2：flip 仍是 1。真实值 0 ^ 1 = 1，跳过。
i = 3：flip ^= diff[3] = 1，flip 变 0（第一次翻转到此失效）。真实值 1 ^ 0 = 1，跳过。
i = 4：flip = 0，真实值 0 ^ 0 = 0，翻转。4 + 3 = 7 <= 8，合法。answer = 2，flip = 1，diff[7] ^= 1。
i = 5：flip = 1，真实值 1 ^ 1 = 0，翻转。5 + 3 = 8 <= 8，恰好合法。answer = 3，flip = 0，diff[8] ^= 1。
i = 6：diff[6] = 0，flip 仍是 0。真实值 1 ^ 0 = 1，跳过。
i = 7：flip ^= diff[7] = 1，flip 变 1。真实值 0 ^ 1 = 1，跳过。
返回 3，与预期一致。注意 i = 5 那一步：原值是 1，但因为被前一次翻转覆盖成了 0，所以仍需翻转——这正是 flip 存在的意义。

最后看无解用例 nums = [1,1,0]、k = 2：i = 0、i = 1 真实值都是 1 跳过；i = 2 真实值为 0 需翻转，但 2 + 2 = 4 > 3，返回 -1。

代码实现

class Solution {
    public int minKBitFlips(int[] nums, int k) {
        int n = nums.length;
        // diff[i] 为 1 表示有一次翻转在位置 i 处失效。
        int[] diff = new int[n + 1];
        // flip 表示当前位置累计被翻转次数的奇偶性。
        int flip = 0;
        int answer = 0;

        for (int i = 0; i < n; i++) {
            flip ^= diff[i];
            if ((nums[i] ^ flip) == 0) {
                // 只有以 i 为起点才能修正位置 i，放不下就无解。
                if (i + k > n) {
                    return -1;
                }
                answer++;
                flip ^= 1;
                diff[i + k] ^= 1;
            }
        }
        return answer;
    }
}

func minKBitFlips(nums []int, k int) int {
    n := len(nums)
    // diff[i] 为 1 表示有一次翻转在位置 i 处失效。
    diff := make([]int, n+1)
    // flip 表示当前位置累计被翻转次数的奇偶性。
    flip := 0
    answer := 0

    for i := 0; i < n; i++ {
        flip ^= diff[i]
        if (nums[i]^flip) == 0 {
            // 只有以 i 为起点才能修正位置 i，放不下就无解。
            if i+k > n {
                return -1
            }
            answer++
            flip ^= 1
            diff[i+k] ^= 1
        }
    }
    return answer
}

复杂度分析

时间复杂度：$O(n)$。凭什么：只有一层从 0 到 n - 1 的循环，循环体内是常数次异或、比较与自增，翻转不再逐位修改数组而是压缩成两次 $O(1)$ 的标记，彻底消掉了朴素做法里的 k 这一维。

空间复杂度：$O(n)$。凭什么：diff 数组长度为 n + 1，是唯一的辅助结构；其余只有 flip、answer 等标量。若改用队列记录「未失效翻转的起点」，空间可降到 $O(k)$，但常数与实现复杂度都更高。

关键点总结

「区间取反、顺序无关」的题目要先把结论提炼成「每个位置只关心被覆盖次数的奇偶」，这一步把操作序列问题降成计数问题，后面才谈得上优化。

贪心的正确性论证套路是找「无选择的位置」：最左端的位置只可能被唯一一个起点覆盖，因此它的处理方式被完全确定；处理完之后子问题同型，归纳即可。这套论证和 954、955 是同一个模式。

差分把「区间加/区间取反」摊成两次单点标记，是把 $O(nk)$ 降到 $O(n)$ 的标准手段；只关心奇偶时用异或代替加减，既省一次取模也让代码更短。

flip ^= diff[i] 必须写在循环体最前面。凡是「先剔除过期影响、再基于当前状态决策」的滑动结构，剔除都要排在决策之前。

无解的判定要落在「必须操作却操作不了」的那一刻，而不是等扫完再检查残留的 0；前者能给出准确的 -1，后者会在某些用例上把已被修正的位置误判。

面试视角：先讲贪心为什么正确（最左位置的唯一起点论证），再讲为什么不能真的翻数组（$O(nk)$ 超时），最后引出差分与奇偶。三段推理缺一不可，尤其第一段是这题的难点所在；若被追问空间优化，可以提用队列保存仍在生效的翻转起点，队首过期就弹出，空间从 $O(n)$ 降到 $O(k)$。

易错点总结

错误写法：真的逐位翻转数组 → 用例 n = 10^5、k = 5 \times 10^4 且需要大量翻转时，总操作量达 $10^9$ 级别，超时。

错误写法：漏掉 flip ^= 1 → 用例 [0,1,0]、k = 1 中位置 0 决定翻转后 flip 仍是 0，当前位置没被修正；由于扫描不再回头，错误无法被发现，答案偏小且结果数组并非全 1。

错误写法：漏掉 diff[i + k] ^= 1 → 用例 [0,0,0,1,0,1,1,0]、k = 3 中第一次翻转的影响一直延续到末尾，i = 3 处真实值被算成 0 而多翻一次，答案从 3 变成更大的值。

错误写法：把 flip ^= diff[i] 写在判断之后 → 用例 [0,0,0,1,0,1,1,0]、k = 3 中 i = 3 时旧的翻转还没失效，真实值算成 1 ^ 1 = 0，多出一次翻转。

错误写法：无解条件写成 i + k >= n → 用例 [0,0,0,1,0,1,1,0]、k = 3 中 i = 5 时 5 + 3 = 8 等于 n，本是合法的最后一个起点，却被误判为无解返回 -1。

错误写法：无解条件写成 i + k > n - 1 → 同样把最后一个合法起点排除，用例 [0]、k = 1 直接返回 -1，而正确答案是 1。

错误写法：diff 数组只开 n 长度 → 用例 [0]、k = 1 中 diff[1] 越界，Java 抛数组越界异常，Go 直接 panic。

错误写法：判断条件写成 nums[i] == 0 而忽略 flip → 用例 [0,0,0,1,0,1,1,0]、k = 3 中 i = 5 的原值是 1，但已被翻成 0，漏翻导致最终并非全 1，答案偏小。

错误写法：用加法维护 flip 却忘记对 2 取模 → 用例中被多次覆盖的位置累计值超过 1，nums[i] ^ flip 的异或语义被破坏，判定结果随机。

错误写法：扫描结束后再遍历一遍数组检查是否全 1 来决定返回 -1 → 用例 [1,1,0]、k = 2 中确实能检出，但由于扫描中未修改原数组，这一遍检查看到的还是原始值，判定完全失效。

错误写法：从右往左扫描 → 用例 [0,0,0,1,0,1,1,0]、k = 3 中「最右位置只能由唯一起点覆盖」的论证不成立（右端的位置可以被多个起点覆盖），贪心失去唯一性，答案偏大。

错误写法：认为答案与 0 的个数直接相关，比如返回 零的个数 / k 向上取整 → 用例 [0,1,0]、k = 1 侥幸正确，但 [0,0,0,1,0,1,1,0]、k = 3 中 0 有四个，公式给出 2，正确答案是 3。

相似题目

题目	难度	考察点
1109. 航班预订统计	中等	差分数组的入门题，区间加用加减而非异或，无需贪心决策
1094. 拼车	中等	差分统计区间占用并校验上限，练的是「区间摊成端点标记」的同一手法
1526. 形成目标数组的子数组最少增加次数	困难	同为区间操作求最少次数，但区间长度任意，答案由相邻差的正增量之和给出
1004. 最大连续1的个数 III	中等	也是 0/1 数组加翻转预算，但用滑动窗口求最长区间而不是求操作次数
453. 最小操作次数使数组元素相等	中等	靠等价变换把「给 n-1 个数加一」转成「给一个数减一」，考的是模型转换
861. 翻转矩阵后的得分	中等	同为翻转类贪心，按位权从高到低逐列决策，每步同样没有选择余地