元宝 快速思考 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[i1] - a[i]中所有正数之和ans \sum_{i0}^{n} \max(0,\ a[i1]-a[i])步骤含义a[0] 0起始基准面a[i1] - 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[i1] long delta cur - prev; // a[i1] - a[i] if (delta 0) { ans delta; } prev cur; } // 尾部虚拟的 a[n1] 0delta 0 - prev long delta -prev; if (delta 0) { ans delta; } return ans; } }⚠️ 如果你的版本签名是ListInteger把nums.get(i)/target.get(i)替换即可注意转long防溢出。 举个例子走一遍nums [1,3,2], target [2,1,4]idiff[i] target-numscurprev→curΔcur-prev累计 ans初始—prev0——00110→11✅11-2-21→-2-31222-2→24✅5尾部—02→0-25答案 5✓ 匹配示例⏱️ 复杂度时间O(n) 单次扫描空间O(1) 只存变量这个差分补零的技巧其实是此类子数组统一增减题目的通用套路同类还有 LC 1526记住一句话就够操作次数 高度剖面所有上行台阶的爬升量之和。