【数据结构-差分】【贪心】力扣1526. 形成目标数组的子数组最少增加次数

给你一个整数数组 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^5
1 <= target[i] <= 10^5

方法一：暴力（超时）

class Solution {
public:
    int minNumberOperations(vector<int>& target) {
        int n = target.size();
        int ans = 0;
        for(int i = 0; i < n; i++){
            while(target[i] != 0){
                int j = i;
                while(j < n && target[j] != 0)
                {
                    target[j]--;
                    j++;
                }
                ans++;
            }
        }
        return ans;
    }
};

最开始想到的是暴力的方法，遍历数组每一个元素，如果他不是0的话，就令从他开始往右的元素都减1，直到有元素0停止。
这个方法由于是三重循环，超出了时间限制，无法完成所有测试。

方法二：贪心

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

官解中将该方法称作差分，我觉得称为贪心更合适。
在这道题中，我们要找的实际上就是递增的区间，然后将区间的最大值减去最小值，将所有递增区间的最大值减去最小值的差加在一起，就是答案。

举个例子：target = [3,1,1,2]
我们要找的实际上有两个递增区间，一个是[3]（第一个区间的最小值默认为0），他最大值3减去最小值0的差为3，第二个递增区间是[1,2]，2-1=1，所以差为1。最后答案就是3+1=4。

实际上找递减区间也是可以的，比如递减区间[3,1]，差是2，递减区间[2]（默认最小值0），差是2，结果也是4。

拿递增区间为例子，两个递增区间之间有什么关系，为什么要找递增区间呢？首先我们拿单独一个递增区间来看，我们需要构造出他的最大元素，我们就要进行不断加一的操作，那么在构造出这个最大元素完毕后，会对后面的区间造成什么影响呢？这取决于递增区间最后一个元素的下一个元素，他决定了下一个递增区间受之前操作的影响。

为什么我们不管递减区间？在例子target = [1,2,3,2,1]中，递减区间[2,1]完全可以被第一个递增区间的操作所覆盖，所以我们不用记录递减区间的操作。

原文地址：https://blog.csdn.net/sjsjs11/article/details/142418501

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！