【C++差分数组】1526. 形成目标数组的子数组最少增加次数|1872
本文涉及知识点
LeetCode1526. 形成目标数组的子数组最少增加次数
给你一个整数数组 target 和一个数组 initial ，initial 数组与 target 数组有同样的维度，且一开始全部为 0 。
请你返回从 initial 得到 target 的最少操作次数，每次操作需遵循以下规则：
在 initial 中选择 任意 子数组，并将子数组中每个元素增加 1 。
答案保证在 32 位有符号整数以内。
示例 1：
输入：target = [1,2,3,2,1]
输出：3
解释：我们需要至少 3 次操作从 intial 数组得到 target 数组。
[0,0,0,0,0] 将下标为 0 到 4 的元素（包含二者）加 1 。
[1,1,1,1,1] 将下标为 1 到 3 的元素（包含二者）加 1 。
[1,2,2,2,1] 将下表为 2 的元素增加 1 。
[1,2,3,2,1] 得到了目标数组。
示例 2：
输入：target = [3,1,1,2]
输出：4
解释：(initial)[0,0,0,0] -> [1,1,1,1] -> [1,1,1,2] -> [2,1,1,2] -> [3,1,1,2] (target) 。
示例 3：
输入：target = [3,1,5,4,2]
输出：7
解释：(initial)[0,0,0,0,0] -> [1,1,1,1,1] -> [2,1,1,1,1] -> [3,1,1,1,1]
-> [3,1,2,2,2] -> [3,1,3,3,2] -> [3,1,4,4,2] -> [3,1,5,4,2] (target)。
示例 4：
输入：target = [1,1,1,1]
输出：1
提示：
1 <= target.length <= 105
1 <= target[i] <= 105
差分数组
性质一：二维数组v，记录所有的操作次数。v[i] = {lefti,righti}表示将inital[lefti…righti]全加1。我们改变v各元素的顺序显然不影响结果。我们将v按升序排序。
性质二：令v1是inital[0…i1]的解，我们将[leftx,i1]延长到i1+1，inital[0…i1]仍然是合法的。
总结：
至少需要nums[0]次操作次数。
如果nums[i-1] >= nums[i]，则 将nums[i-1]的操作延长到i。故不需要额外的操作次数。
如果nums[i-1] < nums[i]。则需要nums[i]-nums[i-1]次操作。
故nums[i] 需要max(0,nums[i]-nums[i-1])次操作。
就是差分数组中正数的和。
代码
核心代码
class Solution {
public:
int minNumberOperations(vector<int>& target) {
int iNeed = 0 ,cur=0;
for(const auto& n : target)
{
if( n > cur)
{
iNeed += n - cur;
}
cur = n;
}
return iNeed;
}
};
单元测试
vector<int> target;
TEST_METHOD(TestMethod11)
{
target = { 1, 2, 3, 2, 1 };
auto res = Solution().minNumberOperations(target);
AssertEx(3, res);
}
TEST_METHOD(TestMethod12)
{
target = { 3,1,1,2 };
auto res = Solution().minNumberOperations(target);
AssertEx(4, res);
}
TEST_METHOD(TestMethod13)
{
target = { 3,1,5,4,2 };
auto res = Solution().minNumberOperations(target);
AssertEx(7, res);
}
TEST_METHOD(TestMethod14)
{
target = { 1,1,1,1 };
auto res = Solution().minNumberOperations(target);
AssertEx(1, res);
}
扩展阅读
| 我想对大家说的话 |
|---|
| 工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。 |
| 学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作 |
| 有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注 |
| 闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。 |
| 如果程序是一条龙，那算法就是他的是睛 |
| 失败+反思=成功 成功+反思=成功 |
视频课程
先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。
原文地址：https://blog.csdn.net/he_zhidan/article/details/142095330
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！