995. K 连续位的最小翻转次数（Rating 1835）

以下内容偏向于记录个人练习过程及思考，非常规题解内容

题目

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

Rating 1835

思路

首先想清楚翻转策略。

如果一个数组能够全部翻转成1，那么我们从左向右按照顺序，看见0就翻转，则一定能获得全1

模拟这个过程的话复杂度是O(nk)，需要考虑复杂度更低的算法。

本质是

遍历到每个数字是，我们需要知道这个数字在之前的翻转过程中跟着翻转了几次

那么我们就知道当前数字的状态了。

维护每个位置对应的翻转次数。

当翻转第i个位置时，我们需要将i,i+1,…,i+k-1这些位置的翻转次数同时加1

而差分数组恰好可以非常轻松的做到这点。

代码

class Solution:
    def minKBitFlips(self, nums: List[int], k: int) -> int:
        n = len(nums)
        d = [0] * (n + 1) # 差分数组
        cnt = [0] * n # 每个位置的翻转次数
        ret = 0
        for idx in range(n):
            if idx == 0:
                cnt[idx] = d[idx] 
            else:
                cnt[idx] = cnt[idx - 1] + d[idx] # 差分数组的前缀和即为当前位置的总翻转次数
            if cnt[idx] % 2 == nums[idx]: # 如果当前位置，经过总翻转次数后为0,则需要再翻转一次
                if idx < n - k + 1: # 还有k个位置可以供翻转
                    d[idx] += 1 # 维护差分数组
                    d[idx + k] -= 1 # 维护差分数组
                    ret += 1 # 翻转总次数+1
                    cnt[idx] = cnt[idx - 1] + d[idx] # ！！！因为当前位置又翻转了一次，所以当前位置的总翻转次数也需要重新维护
                else: # 已经没有k个位置可以供翻转了，无法达成目标
                    return -1
        return ret