题目描述
给你两个长度相同的正整数数组 nums
和 target
。
在一次操作中,你可以选择 nums
的任何 子数组,并将该子数组内的每个元素的值增加或减少 1。
返回使 nums
数组变为 target
数组所需的 最少 操作次数。
样例
输入: 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]。
输入: 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 <= 10^5
1 <= nums[i], target[i] <= 10^8
算法
(贪心) $O(n)$
- 将
target
数组减去nums
,得到每个位置期望修改的值。 - 显然,一段正值和一段负值,是不可能有公用的操作的,否则总代价将会变大。
- 将目标数组按照正负区间划分为不相交的若干个子区间,每个子区间都视为操作一段正值(如果是负值则取相反数)。
- 对于区间 $[l, r]$,显然需要先操作 $target(l)$ 次,然后遍历区间。如果 $target(i + 1) > target(i)$,则 $i + 1$ 位置至少需要额外付出 $target(i + 1) - target(i)$ 次操作。其余情况,$i + 1$ 位置都可以被 $i$ 或之前的位置顺带操作。
时间复杂度
- 划分区间后,每个子区间遍历一次,故总时间复杂度为 $O(n)$。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
#define LL long long
class Solution {
private:
LL solve(int l, int r, vector<int> &target) {
for (int i = l; i <= r; i++)
if (target[i] < 0)
target[i] = -target[i];
LL res = target[l];
for (int i = l; i < r; i++)
res += max(target[i + 1] - target[i], 0);
return res;
}
public:
LL minimumOperations(vector<int>& nums, vector<int>& target) {
const int n = nums.size();
for (int i = 0; i < n; i++)
target[i] -= nums[i];
LL ans = 0;
for (int i = 1, j = 0; i <= n; i++) {
if (i < n && (
target[i] <= 0 && target[i - 1] <= 0
|| target[i] >= 0 && target[i - 1] >= 0)
)
continue;
ans += solve(j, i - 1, target);
j = i;
}
return ans;
}
};