0995. K 连续位的最小翻转次数【困难】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 贪心 + 差分数组

1. 📝 题目描述

• leetcode

给定一个二进制数组 nums 和一个整数 k。

k 位翻转就是从 nums 中选择一个长度为 k 的子数组，同时把子数组中的每一个 0 都改成 1，把子数组中的每一个 1 都改成 0。

返回数组中不存在 0 所需的最小 k 位翻转次数。如果不可能，则返回 -1。

子数组是数组的连续部分。

---

示例 1：

输入：nums = [0,1,0], K = 1
输出：2

解释：
先翻转 A[0]，然后翻转 A[2]。

---

示例 2：

输入：nums = [1,1,0], K = 2
输出：-1

解释：
无论我们怎样翻转大小为 2 的子数组，我们都不能使数组变为 [1,1,1]。

---

示例 3：

输入：nums = [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 <= nums.length <= 10^5
• 1 <= k <= nums.length

2. 🎯 s.1 - 贪心 + 差分数组

js

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var minKBitFlips = function (nums, k) {
  const n = nums.length
  let count = 0 // 翻转次数
  let flipped = 0 // 当前位置被翻转的次数(奇偶性)
  const diff = new Array(n + 1).fill(0) // 差分数组

  for (let i = 0; i < n; i++) {
    // 更新当前位置的翻转状态
    flipped += diff[i]

    // 计算当前位置的实际值(原值 XOR 翻转次数的奇偶性)
    const current = (nums[i] + flipped) % 2

    // 如果当前位置是 0,需要翻转
    if (current === 0) {
      // 检查是否有足够的空间进行翻转
      if (i + k > n) return -1

      count++
      flipped ^= 1 // 当前位置翻转状态改变
      diff[i + k] -= 1 // k 位置后翻转状态恢复
    }
  }

  return count
}

• 时间复杂度:$O(n)$,其中 n 是数组长度,只需遍历一次数组
• 空间复杂度:$O(n)$,差分数组的空间开销

算法思路:

• 贪心策略:从左到右遍历,遇到 0 就必须翻转,因为后续操作无法影响当前位置
• 差分数组优化:用差分数组记录翻转区间的影响,避免每次翻转都修改 k 个元素
• 翻转状态维护:用 flipped 变量维护当前位置被翻转的次数奇偶性
• 实际值计算:当前位置的实际值为 (nums[i] + flipped) % 2,翻转偶数次相当于没翻转
• 边界检查:如果在位置 i 需要翻转但 i + k > n,说明无法完成翻转,返回 -1