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
Solution: Track Last
Time complexity: O(n)
Space complexity: O(1)
C++
1 2 3 4 5 6 7 8 9 10 11 12 |
class Solution { public: int minOperations(vector<int>& nums) { int ans = 0, last = 0; for (int x : nums) if (x <= last) ans += ++last - x; else last = x; return ans; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment