【数学】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 <= 10⁵
1 <= target[i] <= 10⁵

分析

时间复杂度: o(n)
target[0] 需要增加target[0]次，也就是对子数组[0,0]这些target[0]次加一操作。
target[1] 有两种选择：
一，将[0,0]延长到[0,1]。
二，增加新操作[1,1]。
显然优先使用选择一，不增加操作。
当i>1，类似：
一，将[0,i-1] [1,i-1]… 延长到[?,i]。这些子数组的数量，一定是target[i-1]，否则无法达到目标。最多延长target[i-1]次。
二，新增加操作。

代码

很简洁，无需测试用例。

 class Solution {
   
 public:
	 int minNumberOperations(vector<int>& target) {
   
		 target.insert(target.begin(), 0);
		 int iNum = 0;
		 for (int i = 1; i < target.size(); i++)
		 {
   
			 if (target[i] > target[i - 1])
			 {
   
				 iNum += (target[i] - target[i - 1]);
			 }
		 }
		 return iNum;
	 }
 };

贪心+差分数组

cur 是差分数组，当前值：

综上所述： cur总是等于n。

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;
    }
};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用C++ 实现。