文章内容
https://leetcode.cn/problems/minimum-number-of-k-consecutive-bit-flips/description/
一、题目解析
1.1 贪心策略
从左往右扫。走到 i，如果这一位当前是 0，就必须以 i 为左端点翻一次 [i, i+k-1]。
翻转区间长度固定 k，能覆盖 i 的区间左端点只可能落在 [i-k+1, i] 里。而 i 左边的位置已经全被处理成 1 了，任何左端点小于 i 的翻转都会把它们再翻回去。能用的起点只剩 i 一个。错过这一次，i 就永远是 0。
反过来，i 当前已经是 1 就不翻——翻了只是浪费操作，还得再翻回来。
1.2 为什么不能直接模拟
每次翻转都真去改 k 个元素，最坏情况 N 次翻转乘每次 k 步，O(N*K)。这题 N 和 K 都能到 10^5，乘起来 10^10，必 TLE。所以翻转本质上就是区间加 1 再对 2 取模，区间修改要 O(1)即可。
二、差分数组模板
差分数组解决同一类问题：对数组做很多次区间加，中途不关心结果，最后才要答案。每次区间加都老实遍历是 O(r-l+1)，用差分能压到 O(1)。
int n = a.length;int[] diff = new int[n + 2]; // 开 n+2，给 r+1 留余量 // 1. 建差分数组：diff[i] = a[i] - a[i-1]diff[0] = a[0];for (int i = 1; i < n; i++) { diff[i] = a[i] - a[i - 1];} // 2. 区间修改：a[l..r] 每一位加 val，只动两个格子diff[l] += val;diff[r + 1] -= val; // 3. 前缀和还原：跑一遍就拿回修改后的数组for (int i = 1; i < n; i++) { diff[i] += diff[i - 1];}关键在第二步和第三步的配合。diff[l] += val 让 l 及其右边全部抬高 val，diff[r+1] -= val 再把 r 右边多抬的那截压回去，中间刚好留下 [l, r]。还原就是求前缀和，一遍搞定。
三、在线差分：currentFlips 动态前缀和
3.1 这道题和普通差分题的区别
模板里的差分是离线的：所有区间修改先打到 diff 上，全部打完再统一跑一遍前缀和，最后看结果。修改和查询分成前后两个阶段，互不干扰。
这题不行。走到 i 的时候就得知道 nums[i] 现在是 0 还是 1，因为要靠它做决策，而这个"现在"取决于前面所有翻转累积下来的影响。修改和查询交织在同一次遍历里。
3.2 currentFlips 变量
于是把还原前缀和这个动作拆开，边走边算——这就是代码里 currentFlips 的灵魂所在。它是一个跟着 i 往前挪的动态前缀和，值等于"i 这个位置被翻转过的总次数"。
每走到一个 i，做三件事：
- 先
currentFlips += diff[i]，把之前那些操作在 i 处的影响接上来。过期区间的 -1 也是在这一步生效的。 - 判断
(nums[i] + currentFlips) % 2 == 0。原值加翻转次数是偶数，说明翻了等于没翻，当前是 0，必须操作。 - 决定翻转，就在 diff[i] 上加 1、diff[i+k] 上减 1，同时手动让
currentFlips += 1。这个手动加省不得：循环开头那次累加已经过去了，本次对 diff[i] 的修改赶不上那趟车，只能自己补进去。
四、代码逐段解析
class Solution { public int minKBitFlips(int[] nums, int k) { int n = nums.length; // 差分数组开 n+2，给右端点标记留出越界余量 int[] diff = new int[n + 2]; int currentFlips = 0; // 动态前缀和：i 处累计被翻转的次数 int ans = 0; for (int i = 0; i < n; i++) { currentFlips += diff[i]; // 差分累加成当前位置的前缀和 // 原值 + 翻转次数为偶数 => 当前是 0，必须以 i 为起点翻一次 if ((nums[i] + currentFlips) % 2 == 0) { // 翻转区间伸出了数组右边界，无解 if (i + k + 1 >= n + 2) { return -1; } ans++; diff[i] += 1; // 区间左端点，抬高 diff[i + k] -= 1; // 区间右端点之后，压回 currentFlips += 1; // 补上本次修改，循环开头的累加已经错过它 } } return ans; }}diff 为什么开 n+2。 会往右够的只有右端点标记那一格。i 最大 n-1，写入下标 i+k 在越界判断兜住之后最大到 n；如果按 1-indexed 的写法把标记放在 i+k+1，就正好顶到 n+1。开 n+2 把两种写法都覆盖了，不用为下标反复推导。
循环开头的累加在干什么。 currentFlips += diff[i] 就是模板第三步 diff[i] += diff[i-1] 的等价形式，只是把结果存进变量而不是写回数组。写成 diff[i+1] += diff[i] 也一样成立——把当前位置的前缀和推给下一格，下一轮直接读就是答案。两种写法本质相同，用变量更省事，也更清楚地表达"这是个跟着指针走的在线量"。
判断条件的数学推导。 nums[i] 是 0 或 1，每翻一次取反一次，翻 t 次之后的值是 (nums[i] + t) % 2。这个值为 0 就说明当前位是 0，需要翻。currentFlips 存的正是 t，条件因此写成 (nums[i] + currentFlips) % 2 == 0。写成异或 (nums[i] ^ (currentFlips & 1)) == 0 是一回事。
ans++ 和 currentFlips++ 为什么要手动。 ans 是答案计数，每决定翻一次就加一，没有别处替它加。currentFlips 前面说过，是为了让本次翻转对 i 自己立即生效，不加的话紧接着这一位在逻辑上还是 0，状态就乱了。顺带一提，diff[i] += 1 这行其实是为了让 diff 保持自洽——currentFlips 已经手动补过，i 之后不会再读 diff[i]，真正必需的只有 diff[i + k] -= 1。
i + k + 1 >= n + 2 是什么意思。 化简就是 i + k > n。翻转区间是 [i, i+k-1]，合法要求 i+k-1 <= n-1，也就是 i+k <= n。不满足说明区间右端伸到了数组外面，而 nums[i] 又非翻不可，没有别的起点可选，直接返回 -1。判断放在 ans++ 之前，避免多算一次无效操作。
五、复杂度分析
时间 O(N)。一次遍历，循环体全是常数操作，区间修改被差分压成了两次赋值。
空间 O(N)。一个长度 n+2 的 diff 数组，加几个标量。
本文由 AgentPlanFlow 生成