元宝 快速思考 LeetCode 3229. 使数组等于目标数组所需的最少操作次数 Java实现
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])| 步骤 | 含义 |
|---|---|
a[0] = 0 | 起始基准面 |
a[i+1] - a[i] > 0 | 第 i 步有一个向上的台阶，需要额外那么多层操作 |
a[n] → 0 | 最后要把尾部差值归零 |
✅ 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]
| i | diff[i] = target-nums | cur | prev→cur | Δ=cur-prev | 累计 ans |
|---|---|---|---|---|---|
| 初始 | — | prev=0 | — | — | 0 |
| 0 | 1 | 1 | 0→1 | +1✅ | 1 |
| 1 | -2 | -2 | 1→-2 | -3 | 1 |
| 2 | 2 | 2 | -2→2 | +4✅ | 5 |
| 尾部 | — | 0 | 2→0 | -2 | 5 |
答案 =5✓ 匹配示例
⏱️ 复杂度
| 时间 | O(n) 单次扫描 |
| 空间 | O(1) 只存变量 |
这个差分补零的技巧其实是此类"子数组统一增减"题目的通用套路（同类还有 LC 1526），记住一句话就够：操作次数 = 高度剖面所有上行台阶的爬升量之和。