You are given an integer array
nums (0-indexed). In one operation, you can choose an element of the array and increment it by
- For example, if
nums = [1,2,3], you can choose to increment
nums = [1,3,3].
Return the minimum number of operations needed to make
nums strictly increasing.
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.
Input: nums = [1,1,1] Output: 3 Explanation: You can do the following operations: 1) Increment nums, so nums becomes [1,1,2]. 2) Increment nums, so nums becomes [1,2,2]. 3) Increment nums, so nums becomes [1,2,3].
Input: nums = [1,5,2,4,1] Output: 14
Input: nums =  Output: 0
1 <= nums.length <= 5000
1 <= nums[i] <= 104
Iterate the list and whenever find a number is no greater than the previous one, increase that number and count the operations.
class Solution: def minOperations(self, nums: List[int]) -> int: count = 0 if len(nums) < 2: return count prev = None for i, num in enumerate(nums): if prev and num <= prev: count += prev - num + 1 nums[i] = prev + 1 prev = nums[i] return count
- Time Complexity: O(N).
- Space Complexity: O(1).