Question

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 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] <= 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)$.

class Solution:
  def minOperations(self, nums: List[int]) -> int:
    ans = mx = 0
    for v in nums:
      ans += max(0, mx + 1 - v)
      mx = max(mx + 1, v)
    return ans

class Solution {
  public int minOperations(int[] nums) {
    int ans = 0, mx = 0;
    for (int v : nums) {
      ans += Math.max(0, mx + 1 - v);
      mx = Math.max(mx + 1, v);
    }
    return ans;
  }
}

class Solution {
public:
  int minOperations(vector<int>& nums) {
    int ans = 0, mx = 0;
    for (int& v : nums) {
      ans += max(0, mx + 1 - v);
      mx = max(mx + 1, v);
    }
    return ans;
  }
};

func minOperations(nums []int) (ans int) {
  mx := 0
  for _, v := range nums {
    ans += max(0, mx+1-v)
    mx = max(mx+1, v)
  }
  return
}

function minOperations(nums: number[]): number {
  let ans = 0;
  let max = 0;
  for (const v of nums) {
    ans += Math.max(0, max + 1 - v);
    max = Math.max(max + 1, v);
  }
  return ans;
}

impl Solution {
  pub fn min_operations(nums: Vec<i32>) -> i32 {
    let mut ans = 0;
    let mut max = 0;
    for &v in nums.iter() {
      ans += (0).max(max + 1 - v);
      max = v.max(max + 1);
    }
    ans
  }
}

public class Solution {
  public int MinOperations(int[] nums) {
    int ans = 0, mx = 0;
    foreach (int v in nums) {
      ans += Math.Max(0, mx + 1 - v);
      mx = Math.Max(mx + 1, v);
    }
    return ans;
  }
}

#define max(a, b) (((a) > (b)) ? (a) : (b))

int minOperations(int* nums, int numsSize) {
  int ans = 0;
  int mx = 0;
  for (int i = 0; i < numsSize; i++) {
    ans += max(0, mx + 1 - nums[i]);
    mx = max(mx + 1, nums[i]);
  }
  return ans;
}