【差分数组】个人练习-Leetcode-3229. Minimum Operations to Make Array Equal to Target
题目链接:https://leetcode.cn/problems/minimum-operations-to-make-array-equal-to-target/description/
题目大意:给出两个数组nums[]
和target[]
,可以对nums[]
数组进行这样两种操作
- 给某个区间内的子列全加1
- 给某个区间内的子列全减1
求让nums[]
和target[]
相等的最小操作次数。
思路:实际上就是让a[] = target[] - nums[]
这个数组全为0,操作同样适用在a[]
上。考虑到这样一个事实:对于数组的某个区间的统一操作,相当于对于差分数组的两个区间端点做操作。因此构造a[]
的差分数组d[]
。那么对a[i]
到a[j-1]
的操作,就相当于对d[i]
和d[j]
进行操作。比如对下面这个数组a[]
的0~2个元素减去1后,d[0]
和d[3]
发生了改变。
a: 1 1 1 -2->a: 0 0 0 -2
d: 1 0 0 -3 2->d: 0 0 0 -2 2
并且对于d[]
的改变,必然是某个d[i] += 1
,某个d[j] -= 1
。因此对于a[]
某个区间进行操作,就相当于对d[]
的两个端点,一个+1,一个-1。
因为最终会将a[]
变为全0,此时d[]
也全为0,那么就要对d[]
进行一对对进行加减。然而反过来考虑,d[]
从全0变为别的样子的时候,也是一对对加减上去的,因此实际上d[]
中的元素之和一定为0。
那么只需要找正的元素个数即可,这就是最佳的方案。非最佳的方案对应着的是,在d[]
的某个元素上+1又-1,这样必然会让操作次数增多。
完整代码
class Solution {
public:
long long minimumOperations(vector<int>& nums, vector<int>& target) {
int n = nums.size();
for (int i = 0; i < n; i++) {
nums[i] = target[i] - nums[i];
}
vector<int> diff(n+1, 0);
diff[0] = nums[0];
for (int i = 1; i < n; i++) {
diff[i] = nums[i] - nums[i-1];
}
diff[n] = -nums[n-1];
long long ans = 0;
for (int i = 0; i <= n; i++) {
ans += max(diff[i], 0);
}
return ans;
}
};
原文地址:https://blog.csdn.net/Rstln/article/details/142793059
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!