LeetCode 3229 — 使数组等于目标数组所需的最少操作次数

📌 题目理解

每次操作：选任意连续子数组，全体 +1 或 -1，求让nums变target的最少步数。

💡 核心转化

令差值数组diff[i] = target[i] - nums[i]

问题等价于：用最少次「对子数组整体 ±1」把diff全消为 0。

关键直觉 —— 画成柱状图

把diff画出来，正数 = 山峰，负数 = 山谷。一次"对子数组 +1"相当于把一段连续的柱子上沿齐平往下削 1（同理 -1 往上填谷）。

• 同号连续段内部的操作可以共享（像阶梯一样一层层削）

• 正负交界处必须断开，不能共享

这意味着：总操作数 = 只看上升沿的爬升总和

🔑 最优雅解法：首尾补零 + 差分

构造虚拟数组a = [0, diff[0], diff[1], ..., diff[n-1], 0]

答案就是a[i+1] - a[i]中所有正数之和：

ans = \sum_{i=0}^{n} \max(0,\ a[i+1]-a[i])

✅ Java 实现

class Solution { public long minimumOperations(int[] nums, int[] target) { int n = nums.length; long ans = 0; // prev 模拟 a[i]，初始 a[0] = 0 long prev = 0; for (int i = 0; i < n; i++) { long cur = (long) target[i] - (long) nums[i]; // diff[i] = a[i+1] long delta = cur - prev; // a[i+1] - a[i] if (delta > 0) { ans += delta; } prev = cur; } // 尾部：虚拟的 a[n+1] = 0，delta = 0 - prev long delta = -prev; if (delta > 0) { ans += delta; } return ans; } }

⚠️ 如果你的版本签名是List<Integer>，把nums.get(i)/target.get(i)替换即可，注意转long防溢出。

🔍 举个例子走一遍

nums = [1,3,2], target = [2,1,4]

答案 =5✓ 匹配示例

⏱️ 复杂度

这个差分补零的技巧其实是此类"子数组统一增减"题目的通用套路（同类还有 LC 1526），记住一句话就够：操作次数 = 高度剖面所有上行台阶的爬升量之和。