本文介绍如何用差分数组优化贪心策略，在线性时间内判断能否通过若干长度为k的子数组统一减1操作，将整数数组全部变为0。核心在于避免重复求最小值和区间更新，将时间复杂度从o(nk)降至o(n)。
本文介绍如何用差分数组优化贪心策略，在线性时间内判断能否通过若干长度为k的子数组统一减1操作，将整数数组全部变为0。核心在于避免重复求最小值和区间更新，将时间复杂度从o(nk)降至o(n)。
在解决“Apply Operations to Make All Array Elements Equal to Zero”这类区间批量修改问题时，直观的滑动窗口+逐次减最小值的方法（如原始代码中反复调用 min(sublist) 并赋值）虽逻辑清晰，但时间复杂度高达 O(nk)，极易超时——尤其当数组长度达 10⁵ 级别时。
根本瓶颈在于：每次窗口移动都重新扫描 k 个元素求最小值，并执行 k 次赋值更新。而真正关键的信息并非“当前窗口最小值是多少”，而是：当处理到位置 i 时，已有多少次操作影响了 nums[i]？ 这正是差分数组（Difference Array）擅长的场景：它能以 O(1) 时间标记一次区间增减，并在遍历中通过前缀和实时还原当前净变化量。
✅ 正确贪心策略：从左到右“按需启动”操作
我们从索引 0 开始遍历数组。对于每个位置 i：
- 先根据差分数组 diff 计算出截至目前对 nums[i] 的累计减量（即 diff[0..i] 前缀和），得到当前实际剩余值 v = nums[i] + diff[i]（注意：diff[i] 存储的是负向变化，故为加法）；
- 若 v
- 若 v > 0 → 必须从此处发起 v 次长度为 k 的减1操作（覆盖 [i, i+k-1]），否则 nums[i] 永远无法归零（左侧已处理完毕，无法再回溯修正）；
- 发起操作前需检查边界：若 i + k > len(nums)，说明无法构造合法子数组覆盖 i，返回 False；
- 使用差分技巧记录该操作：diff[i] -= v（表示从 i 开始减少 v），diff[i + k] += v（表示从 i+k 起撤销影响）。
? 差分数组工作原理（简明版）
设原数组为 nums，我们维护差分数组 diff（长度 n+1，末尾哨兵防越界）。
- 对区间 [l, r] 整体减 v，只需：
diff[l] -= v
diff[r + 1] += v（若 r+1 - 遍历时用 diff[i] += diff[i-1] 动态累加，即可在 O(1) 时间获得位置 i 的总偏移量。
? 参考实现（Python）
class Solution:
def checkArray(self, nums: List[int], k: int) -> bool:
n = len(nums)
diff = [0] * (n + 1) # 差分数组，索引0~n，diff[n]为哨兵
for i in range(n):
# 累加之前所有操作对nums[i]的影响
if i > 0:
diff[i] += diff[i - 1]
# 当前位置的实际剩余值
current = nums[i] + diff[i]
# 不可能为负（过度减）
if current < 0:
return False
# 若需操作，必须从i开始覆盖k个元素
if current > 0:
if i + k > n: # 无法构造长度为k的子数组
return False
# 标记：从i开始减current，到i+k-1结束
diff[i] -= current
diff[i + k] += current
return True⚠️ 关键注意事项
- 贪心合法性：因操作只能减、不能加，且子数组必须连续，故最左侧的非零元素 nums[i] 必须由以 i 为起点的操作来消除——任何以 j
- 差分初始化：diff 初始全0，确保首次遍历时 diff[0] 无干扰；diff[n] 作为哨兵，避免 i+k == n 时访问越界。
- 数值范围：current 可能很大，但算法只做加减与比较，无需额外取模或大数处理。
- 时间/空间复杂度：严格 O(n) 时间、O(n) 空间，满足大规模输入要求。
此方法彻底规避了窗口内重复扫描与原地修改，将问题转化为一次线性扫描 + 常数次差分更新，是处理“固定长度区间批量更新+可行性判定”类问题的经典范式。
