class Solution {
public:
long long minimumOperations(vector<int>& nums, vector<int>& target) {
}
};
100329. 使数组等于目标数组所需的最少操作次数
给你两个长度相同的正整数数组 nums 和 target。
在一次操作中，你可以选择 nums 的任何子数组，并将该子数组内的每个元素的值增加或减少 1。
返回使 nums 数组变为 target 数组所需的 最少 操作次数。
示例 1：
输入： nums = [3,5,1,2], target = [4,6,2,4]
输出： 2
解释：
执行以下操作可以使 nums 等于 target：
- nums[0..3] 增加 1，nums = [4,6,2,3]。
- nums[3..3] 增加 1，nums = [4,6,2,4]。
示例 2：
输入： nums = [1,3,2], target = [2,1,4]
输出： 5
解释：
执行以下操作可以使 nums 等于 target：
- nums[0..0] 增加 1，nums = [2,3,2]。
- nums[1..1] 减少 1，nums = [2,2,2]。
- nums[1..1] 减少 1，nums = [2,1,2]。
- nums[2..2] 增加 1，nums = [2,1,3]。
- nums[2..2] 增加 1，nums = [2,1,4]。
提示：
1 <= nums.length == target.length <= 1051 <= nums[i], target[i] <= 108原站题解
golang 解法, 执行用时: 111 ms, 内存消耗: 8.7 MB, 提交时间: 2024-07-23 22:06:55
func minimumOperations1(nums, target []int) int64 {
s := target[0] - nums[0]
ans := abs(s)
for i := 1; i < len(nums); i++ {
k := (target[i] - target[i-1]) - (nums[i] - nums[i-1])
if k > 0 {
if s >= 0 {
ans += k
} else {
ans += max(k+s, 0)
}
} else {
if s <= 0 {
ans -= k
} else {
ans -= min(k+s, 0)
}
}
s += k
}
return int64(ans)
}
func abs(x int) int { if x < 0 { return -x }; return x }
func minimumOperations(nums, target []int) int64 {
n := len(nums)
ans := max(target[0]-nums[0], 0)
for i := 1; i < n; i++ {
ans += max((target[i]-nums[i])-(target[i-1]-nums[i-1]), 0)
}
ans += max(-(target[n-1] - nums[n-1]), 0)
return int64(ans)
}
java 解法, 执行用时: 1 ms, 内存消耗: 57.5 MB, 提交时间: 2024-07-23 22:06:26
class Solution {
public long minimumOperations1(int[] nums, int[] target) {
long s = target[0] - nums[0];
long ans = Math.abs(s);
for (int i = 1; i < nums.length; i++) {
int k = (target[i] - target[i - 1]) - (nums[i] - nums[i - 1]);
if (k > 0) {
ans += s >= 0 ? k : Math.max(k + s, 0);
} else {
ans -= s <= 0 ? k : Math.min(k + s, 0);
}
s += k;
}
return ans;
}
public long minimumOperations(int[] nums, int[] target) {
int n = nums.length;
long ans = Math.max(target[0] - nums[0], 0);
for (int i = 1; i < n; i++) {
ans += Math.max((target[i] - nums[i]) - (target[i - 1] - nums[i - 1]), 0);
}
ans += Math.max(-(target[n - 1] - nums[n - 1]), 0);
return ans;
}
}
cpp 解法, 执行用时: 160 ms, 内存消耗: 119.4 MB, 提交时间: 2024-07-23 22:05:49
class Solution {
public:
long long minimumOperations1(vector<int>& nums, vector<int>& target) {
long long s = target[0] - nums[0];
long long ans = abs(s);
for (int i = 1; i < nums.size(); i++) {
int k = (target[i] - target[i - 1]) - (nums[i] - nums[i - 1]);
if (k > 0) {
ans += s >= 0 ? k : max(k + s, 0LL);
} else {
ans -= s <= 0 ? k : min(k + s, 0LL);
}
s += k;
}
return ans;
}
long long minimumOperations(vector<int>& nums, vector<int>& target) {
int n = nums.size();
long long ans = max(target[0] - nums[0], 0);
for (int i = 1; i < n; i++) {
ans += max((target[i] - nums[i]) - (target[i - 1] - nums[i - 1]), 0);
}
ans += max(-(target[n - 1] - nums[n - 1]), 0);
return ans;
}
};
python3 解法, 执行用时: 130 ms, 内存消耗: 29.2 MB, 提交时间: 2024-07-23 22:05:14
class Solution:
# 差分数组
def minimumOperations1(self, nums: List[int], target: List[int]) -> int:
s = target[0] - nums[0]
ans = abs(s)
for (a, b), (c, d) in pairwise(zip(nums, target)):
k = (d - c) - (b - a)
if k > 0:
ans += k if s >= 0 else max(k + s, 0)
else:
ans -= k if s <= 0 else min(k + s, 0)
s += k
return ans
# 进一步分析差分数组的性质
def minimumOperations(self, nums: List[int], target: List[int]) -> int:
a = [0] + [t - x for x, t in zip(nums, target)] + [0] # 前后加 0，方便计算
return sum(max(y - x, 0) for x, y in pairwise(a))