1827.md

title	description	keywords
1827. 最少操作使数组递增	LeetCode 1827. 最少操作使数组递增题解，Minimum Operations to Make the Array Increasing，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。	LeetCode 1827. 最少操作使数组递增 最少操作使数组递增 Minimum Operations to Make the Array Increasing 解题思路 贪心 数组

1827. 最少操作使数组递增

🟢 Easy  🔖  贪心 数组  🔗 力扣 LeetCode

题目

You are given an integer array nums (0-indexed). In one operation, you can choose an element of the array and increment it by 1.

• For example, if nums = [1,2,3], you can choose to increment nums[1] to make nums = [1,3,3].

Return the minimum number of operations needed to make nums strictly increasing.

An array nums is strictly increasing if nums[i] < nums[i+1] for all 0 <= i < nums.length - 1. An array of length 1 is trivially strictly increasing.

Example 1:

Input: nums = [1,1,1]

Output: 3

Explanation: You can do the following operations:

1. Increment nums[2], so nums becomes [1,1,2 ].

2. Increment nums[1], so nums becomes [1,2 ,2].

3. Increment nums[2], so nums becomes [1,2,3 ].

Example 2:

Input: nums = [1,5,2,4,1]

Output: 14

Example 3:

Input: nums = [8]

Output: 0

Constraints:

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

题目大意

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

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

请你返回使 nums 严格递增 的 最少 操作次数。

我们称数组 nums 是 严格递增的 ，当它满足对于所有的 0 <= i < nums.length - 1 都有 nums[i] < nums[i+1] 。一个长度为 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. 初始化：

   • 使用一个变量 prev 来记录当前元素应该满足的最小值（即前一个元素的值加 1）。最开始，prev 设置为 0。

2. 遍历数组：

   • 遍历数组中的每个元素：
     • 如果当前元素 num 大于 prev，那么它已经满足递增条件，直接将 prev 更新为当前元素 num。
     • 如果当前元素 num 小于或等于 prev，则需要进行调整。为了使当前元素严格大于 prev，我们将当前元素增加到 prev + 1，并计算所需的操作次数（即 prev + 1 - num）。然后将 prev 更新为 prev + 1，以便接下来继续判断下一个元素。

3. 返回结果：

   • 最终，所有需要进行的操作次数累加起来，即为最少的修改次数。

复杂度分析

• 时间复杂度： O(n)，其中 n 是数组 nums 的长度，只遍历了数组一次，每次操作的时间复杂度为常数级别。
• 空间复杂度： O(1)，只使用了常数的额外空间。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var minOperations = function (nums) {
	let operations = 0;
	let prev = 0;
	for (let num of nums) {
		if (num > prev) {
			prev = num;
		} else {
			operations += prev + 1 - num;
			prev++;
		}
	}
	return operations;
};

相关题目

题号	标题	题解	标签	难度	力扣
945	使数组唯一的最小增量	[✓]	贪心 数组 计数 1+	🟠	🀄️ 🔗
2233	K 次增加后的最大乘积		贪心 数组 堆（优先队列）	🟠	🀄️ 🔗
2263	数组变为有序的最小操作次数 🔒		贪心 动态规划	🔴	🀄️ 🔗
2366	将数组排序的最少替换次数		贪心 数组 数学	🔴	🀄️ 🔗