1827. Minimum Operations to Make the Array Increasing
Description
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 incrementnums[1]
to makenums = [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] <= 104
Solutions
Solution 1: Single Pass
We use a variable $mx$ to record the maximum value of the current strictly increasing array, initially $mx = 0$.
Traverse the array nums
from left to right. For the current element $v$, if $v \lt mx + 1$, we need to increase it to $mx + 1$ to ensure the array is strictly increasing. Therefore, the number of operations we need to perform this time is $max(0, mx + 1 - v)$, which is added to the answer, and then we update $mx=max(mx + 1, v)$. Continue to traverse the next element until the entire array is traversed.
The time complexity is $O(n)$, where $n$ is the length of the array nums
. The space complexity is $O(1)$.
1 2 3 4 5 6 7 |
|
1 2 3 4 5 6 7 8 9 10 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 |
|
1 2 3 4 5 6 7 8 9 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|