本文介绍如何用差分数组优化滑动窗口模拟法，以 o(n) 时间复杂度判断能否通过若干次长度为 k 的子数组减 1 操作，将整数数组全部变为 0。
本文介绍如何用差分数组优化滑动窗口模拟法，以 o(n) 时间复杂度判断能否通过若干次长度为 k 的子数组减 1 操作，将整数数组全部变为 0。
在 LeetCode 题目「Apply Operations to Make All Array Elements Equal to Zero」中，核心约束是：每次只能选择长度恰好为 k 的连续子数组，将其所有元素减 1；操作可执行任意次；目标是让整个数组变为全 0。直观的贪心策略是——从左到右处理，一旦遇到非零值 nums[i]，就必须用以 i 为起点的长度为 k 的子数组来“抵消”它（即执行 nums[i] 次减 1 操作）。否则，nums[i] 将永远无法被后续操作覆盖（因操作不能向左延伸），导致失败。
但若按原始思路暴力模拟（如对每个位置反复取窗口最小值、批量减法、再赋回原数组），时间复杂度会退化至 O(nk)，在大规模输入下必然超时。关键瓶颈在于：重复计算窗口内累计减量，且无法快速反映历史操作对当前位置的影响。
✅ 正确解法是引入 差分数组（Difference Array） 实现 O(1) 区间更新 + O(1) 单点查询：
- 定义 diff[0..n]（长度为 n+1），其中 diff[i] 表示从位置 i 开始的“净减量变化”；
- 维护一个运行变量 curr 表示当前位置 i 已被前面所有操作影响的总减量（即 diff 的前缀和）；
- 遍历 i ∈ [0, n)：
- 更新 curr += diff[i]，得到当前实际已减去的总量；
- 计算当前位置真实剩余值：real = nums[i] + curr（注意：curr 为负值，代表已减去量）；
- 若 real
- 若 real > 0 → 必须从此处启动 real 次新操作：
- 检查是否越界：i + k > n ⇒ 无法覆盖，返回 False；
- 否则，在差分数组中标记：diff[i] -= real（起始减量），diff[i + k] += real（终止补偿）；
该算法单次遍历完成，时间复杂度 O(n)，空间复杂度 O(n)，彻底规避了窗口内 min 查找与数组拷贝开销。
以下是完整、可直接提交的 Python 实现：
class Solution:
def checkArray(self, nums: List[int], k: int) -> bool:
n = len(nums)
diff = [0] * (n + 1) # 差分数组，索引 0~n
curr = 0 # 当前累计减量（即 diff[0..i] 前缀和）
for i in range(n):
curr += diff[i] # 应用位置 i 的差分更新
real = nums[i] + curr # 当前真实剩余值
if real < 0:
return False # 被减成负数，非法
if real > 0:
if i + k > n: # 无法放置长度为 k 的操作区间
return False
diff[i] -= real # 在 i 处开始 real 次减操作
diff[i + k] += real # 在 i+k 处撤销影响
return True⚠️ 注意事项：
- 差分数组 diff 长度必须为 n+1，以安全支持 diff[n] 赋值（避免索引越界）；
- real = nums[i] + curr 中 curr 为负值（表示已减量），因此 real 是剩余待处理值；
- 所有判断（越界、负值）必须在应用当前 real 操作前完成，确保逻辑原子性；
- 无需显式检查最终数组是否为 0 —— 贪心+差分保证：若全程合法，则结尾必全为 0。
总结：本题是差分数组的经典应用场景。它将“多次区间减法”的累积效应压缩为前缀和维护，把原本 O(nk) 的模拟降维至线性。掌握该模式，可高效解决一类“区间增/减 + 贪心决策”的构造性数组问题。
