Hard

题目描述

给你一个整数数组 target。一开始，你有一个大小和 target 相同的数组 initial，其中所有元素都是 0。

在一次操作中，你可以在 initial 中选择任意一个子数组，并将子数组中每个元素增加 1。

请你返回从 initial 出发，最少需要多少次操作可以得到数组 target。

生成的测试用例保证答案可以用 32 位整数表示。

示例 1：

输入：target = [1,2,3,2,1]
输出：3
解释：我们需要至少 3 次操作从 initial 数组得到 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] 得到 target 数组。

示例 2：

输入：target = [3,1,1,2]
输出：4
解释：[0,0,0,0] -> [1,1,1,1] -> [1,1,1,2] -> [2,1,1,2] -> [3,1,1,2]

示例 3：

输入：target = [3,1,5,4,2]
输出：7
解释：[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]。

提示：

  • 1 <= target.length <= 10^5
  • 1 <= target[i] <= 10^5
  • 输入保证答案在 32 位整数范围内。

解题思路

这道题的关键在于理解贪心策略。我们需要找到最优的增加方式，使得操作次数最少。

贪心思路分析：

  1. 观察规律：对于任何连续的子数组，我们应该尽可能地同时增加多个元素，这样可以减少操作次数。

  2. 关键洞察：对于每个位置 i，我们只需要考虑它相对于前一个位置的"额外增加量"。如果 target[i] > target[i-1]，那么需要额外操作 target[i] - target[i-1] 次；如果 target[i] <= target[i-1]，则不需要额外操作，因为之前的操作已经覆盖了这个位置。

  3. 贪心策略：从左到右遍历数组，每当遇到比前一个元素大的值时，我们需要额外进行 target[i] - target[i-1] 次操作。第一个元素需要 target[0] 次操作。

这种方法的正确性在于：我们总是选择最长的可能子数组来进行操作，这样能最大化每次操作的效果。

算法步骤：

  1. 初始化操作次数为第一个元素的值
  2. 从第二个元素开始遍历
  3. 如果当前元素大于前一个元素，增加差值到操作次数中
  4. 返回总操作次数

时间复杂度：O(n)，空间复杂度：O(1)。

代码实现

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

class Solution:
    def minNumberOperations(self, target: List[int]) -> int:
        operations = target[0]
        for i in range(1, len(target)):
            if target[i] > target[i - 1]:
                operations += target[i] - target[i - 1]
        return operations

public class Solution {
    public int MinNumberOperations(int[] target) {
        int operations = target[0];
        for (int i = 1; i < target.Length; i++) {
            if (target[i] > target[i - 1]) {
                operations += target[i] - target[i - 1];
            }
        }
        return operations;
    }
}

/**
 * @param {number[]} target
 * @return {number}
 */
var minNumberOperations = function(target) {
    let operations = target[0];
    for (let i = 1; i < target.length; i++) {
        if (target[i] > target[i - 1]) {
            operations += target[i] - target[i - 1];
        }
    }
    return operations;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历数组一次，n为数组长度
空间复杂度O(1)只使用常数额外空间