LeetCode 3229. 使数组等于目标数组所需的最少操作次数
题目分析
给定 nums 和 target，每次操作可选任意子数组，所有元素同时 +1 或 -1，求最少操作次数。
核心思路：差分数组
设 delta[i] = target[i] – nums[i]，问题转化为：将全零数组通过"区间+1/-1"操作变成 delta 数组。
对 delta 构造差分数组 d：
d[0] = delta[0]
d[i] = delta[i] – delta[i-1] (i ≥ 1)
虚拟位置 d[n] = -delta[n-1]（确保 d 之和为 0）
关键观察：对子数组 [l, r] 执行 +1 操作，等价于 d[l] += 1, d[r+1] -= 1。每次操作恰好修改差分数组的两个位置（一正一负），因此：
最少操作次数 = 差分数组中正数元素之和
举例验证
nums = [3,1,5], target = [1,3,1]
delta = [-2, 2, -4]
d = [-2, 4, -6, 4] (正数和 = 4+4 = 8)
每次操作配对一个正位置减1和一个负位置加1，8次即可。
C 语言实现
long long minimumOperations(int* nums, int numsSize, int* target, int targetSize) {
long long ans = 0;
long long prev = 0; // 上一个 delta 值，初始为 0（虚拟的 delta[-1]）
for (int i = 0; i < numsSize; i++) {
long long curr = (long long)target[i] – nums[i];
if (curr > prev) {
ans += curr – prev; // 差分 d[i] 为正时累加
}
prev = curr;
}
// 处理虚拟位置 d[n] = 0 – delta[n-1] = -prev
// 若 d[n] > 0（即 prev < 0），则需累加
if (prev < 0) {
ans -= prev;
}
return ans;
}
复杂度分析
指标复杂度
时间O(n)
空间O(1)
算法图解
delta: 0 -2 2 -4 0 (首尾补0)
差分 d: -2 4 -6 4
↓ ↓
正数和: 4 + 4 = 8 ← 答案
每次操作：选一正一负配对消除，共需 max(正数和, |负数和|) = 8 次
