形成目标数组的子数组最少增加次数

难度: Hard

给你一个整数数组 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

Submission

运行时间: 59 ms

内存: 25.2 MB

class Solution:
    def minNumberOperations(self, target: List[int]) -> int:
        left = 0
        re = 0
        for num in target:
            if num > left:
                re += num - left
            left = num
        return re

Explain

该题解采用了一种贪心算法的思路。其核心在于逐一处理数组元素，并在每个位置计算相对于前一个元素的增量。如果当前元素值大于前一个元素值（即存在递增），那么这种增量正好代表了在目标数组中，为了达到当前高度所需的额外操作次数。整个算法遍历一次数组，通过逐个元素对比前后差异，累计这些差异即得到了形成目标数组所需的最少操作次数。

时间复杂度: O(n)

空间复杂度: O(1)

class Solution:
    def minNumberOperations(self, target: List[int]) -> int:
        left = 0  # 初始化前一个元素的值为0（因为initial数组全部为0）
        re = 0  # 初始化操作次数为0
        for num in target:  # 遍历target数组
            if num > left:  # 如果当前元素大于前一个元素
                re += num - left  # 增加的操作次数是两者的差
            left = num  # 更新前一个元素值为当前元素值
        return re  # 返回总的操作次数

Explore

在这个问题中，贪心算法通过在每个步骤选择局部最优解（即只在必要时增加操作次数来匹配或超过前一个元素的值）确保找到全局最优解。该方法的有效性源于问题的性质：每个元素只需要考虑与前一个元素的关系，因此累计增量直接反映了整个数组从初始状态到目标状态的最少操作次数。由于每次只增加到必需的最小值，这保证了操作总数不能进一步减少，因此总是能找到全局最优解。

`left`变量的初始值为0是因为题目假设数组的初始状态是所有元素均为0。因此，`left`代表初始元素的值，用以计算第一个元素需要增加的操作次数。这与`initial`数组的初始状态直接相关，因为从0开始计算增量可以确保正确统计将整个数组从全零状态变为目标数组状态所需的最小操作次数。

在当前元素小于或等于前一个元素的情况下，不需要额外的操作是因为目标数组的构建是累积的。如果当前元素小于或等于前一个元素，意味着不需要增加额外的高度来达到目标值。我们只需要关注在必要时增加高度（即当前元素大于前一个元素）来确保数组的形状符合目标数组的要求。

如果`num`比`left`小，那么`num - left`将是一个负数。在这种情况下，由于`re += num - left`这行代码前有一个条件判断`if num > left`，因此如果`num`小于`left`，这个负增量不会被加到`re`上，也就是说，不会减少已累计的操作次数。这种情况不需要特别处理，因为减少数组中的值不需要额外的操作次数，它自然地符合贪心策略的优化目标。