Easy

题目描述

给你一个整数数组 nums（下标从 0 开始）。在一次操作中，你可以选择数组中的一个元素并将它增加 1。

例如，如果 nums = [1,2,3]，你可以选择增加 nums[1] 得到 nums = [1,3,3]。

返回使 nums 严格递增所需的最少操作数。

如果对于所有的 0 <= i < nums.length - 1 都满足 nums[i] < nums[i+1]，则数组 nums 是严格递增的。长度为 1 的数组显然是严格递增的。

示例 1：

输入：nums = [1,1,1]
输出：3
解释：你可以进行如下操作：
1) 增加 nums[2]，数组变为 [1,1,2]
2) 增加 nums[1]，数组变为 [1,2,2]  
3) 增加 nums[2]，数组变为 [1,2,3]

示例 2：

输入：nums = [1,5,2,4,1]
输出：14

示例 3：

输入：nums = [8]
输出：0

约束条件：

  • 1 <= nums.length <= 5000
  • 1 <= nums[i] <= 10^4

解题思路

这是一个典型的贪心问题。要使数组严格递增，我们需要确保每个元素都比前一个元素大至少 1。

贪心策略分析：

为了使操作数最少，我们应该从左到右遍历数组，对于每个位置 i，如果 nums[i] <= nums[i-1]，我们需要将 nums[i] 增加到 nums[i-1] + 1。这样可以保证：

  1. 当前元素满足严格递增的条件
  2. 增加的幅度是最小的，不会影响后续元素的最优选择

算法步骤：

  1. 从第二个元素开始遍历数组
  2. 对于每个元素 nums[i]，如果它不大于前一个元素 nums[i-1]
  3. 计算需要的操作数：nums[i-1] + 1 - nums[i]
  4. 更新 nums[i] 为 nums[i-1] + 1
  5. 累加总操作数

这种贪心策略是正确的，因为我们总是选择使当前元素刚好满足严格递增条件的最小值，这样不会对后续元素造成不必要的约束。

时间复杂度为 O(n)，只需要一次遍历；空间复杂度为 O(1)，只使用常数额外空间。

代码实现

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

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

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

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

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)只需要遍历数组一次，其中 n 是数组长度
空间复杂度O(1)只使用常数额外空间，原地修改数组

相关题目