This article is participating in Python Theme Month. See the link for details

describe

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,2] Increment NUMs [2] So nums becomes [1, 2, 3].Copy the code

Example 2:

Input: nums = [1,5,2,4,1]
Output: 14
Copy the code

Example 3:

Input: nums = [8]
Output: 0
Copy the code

Note:

1 <= nums.length <= 5000
1 <= nums[i] <= 10^4
Copy the code

parsing

The nums is converted to an increment sequence by a specific operation, which is the minimum number of operations required to convert nums to an increment sequence. If the latter element is less than or equal to the previous element, change the latter element to the size of the previous element plus one. Add the number of operations to result. The result obtained at the end of the iteration is the result.

answer

class Solution(object):
    def minOperations(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        result = 0
        i = 1
        while i < len(nums):
            if nums[i] <= nums[i-1]:
                increment = nums[i - 1] - nums[i] + 1
                result += increment
                nums[i] += increment
            i += 1
        return result

        	      
		
Copy the code

The results

Runtime: 108 ms, Faster than 39.07% of Python online submissions for Minimum Operations to Make the Array Increasing. Memory Usage: Submissions in Python online submissions for Minimum Operations to Make the Array Increasing.Copy the code

parsing

If the current element is greater than p, use p; otherwise, increment p by 1 to indicate the smallest number that should exist at the current position. Result is then used to record the number of operations required to increase the current element to the minimum number that should exist. The result is the result at the end of the loop.

answer

class Solution(object): def minOperations(self, nums): """ :type nums: List[int] :rtype: Int """ p,result=0,0 for num in nums: if p < num: p = num else: p += 1 result += p-num return resultCopy the code

The results

Runtime: 92 ms, Faster than 94.77% of Python online submissions for Minimum Operations to Make the Array Increasing. Memory Usage: Submissions in Python online submissions for Minimum Operations to Make the Array Increasing.Copy the code

Original link: leetcode.com/problems/mi…

Your support is my biggest motivation