Skip to content

Latest commit

 

History

History
223 lines (158 loc) · 4.91 KB

README_EN.md

File metadata and controls

223 lines (158 loc) · 4.91 KB
Raw
comments difficulty edit_url rating source tags
true
Easy
1314
Biweekly Contest 50 Q1
Greedy
Array

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.

    <li>For example, if <code>nums = [1,2,3]</code>, you can choose to increment <code>nums[1]</code> to make <code>nums = [1,<u><b>3</b></u>,3]</code>.</li>

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:

    <li><code>1 &lt;= nums.length &lt;= 5000</code></li>

<li><code>1 &lt;= nums[i] &lt;= 10<sup>4</sup></code></li>

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

Python3

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

Java

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;
    }
}

C++

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;
    }
};

Go

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

TypeScript

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;
}

Rust

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
    }
}

C#

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;
    }
}

C

#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;
}