Description
You are given a 0-indexed integer array nums. In one operation you can replace any element of the array with any two elements that sum to it.
- For example, consider
nums = [5,6,7]. In one operation, we can replacenums[1]with2and4and convertnumsto[5,2,4,7].
Return the minimum number of operations to make an array that is sorted in non-decreasing order.
Example 1:
Input: nums = [3,9,3] Output: 2 Explanation: Here are the steps to sort the array in non-decreasing order: - From [3,9,3], replace the 9 with 3 and 6 so the array becomes [3,3,6,3] - From [3,3,6,3], replace the 6 with 3 and 3 so the array becomes [3,3,3,3,3] There are 2 steps to sort the array in non-decreasing order. Therefore, we return 2.
Example 2:
Input: nums = [1,2,3,4,5] Output: 0 Explanation: The array is already in non-decreasing order. Therefore, we return 0.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 109
Solutions
Solution 1: Greedy Approach
We observe that to make the array nums non-decreasing or monotonically increasing, the elements towards the end of the array should be as large as possible. Therefore, it is unnecessary to replace the last element nums[n-1] of the array nums with multiple smaller numbers.
In other words, we can traverse the array nums from the end to the beginning, maintaining the current maximum value mx, initially mx = nums[n-1].
- If the current element nums[i] ≤ mx, there is no need to replace nums[i]. We simply update mx = nums[i].
- Otherwise, we need to replace nums[i] with multiple numbers that sum to nums[i]. The maximum of these numbers is mx, and the total number of replacements is k=\left \lceil nums[i]⁄mx \right \rceil. Therefore, we need to perform k-1 operations, which are added to the answer. Among these k numbers, the smallest number is \left \lfloor nums[i]⁄k \right \rfloor. Therefore, we update mx = \left \lfloor nums[i]⁄k \right \rfloor.
After the traversal, we return the total number of operations.
The time complexity is O(n), where n is the length of the array nums. The space complexity is O(1).
class Solution: def minimumReplacement(self, nums: List[int]) -> int: ans = 0 n = len(nums) mx = nums[-1] for i in range(n - 2, -1, -1): if nums[i] <= mx: mx = nums[i] continue k = (nums[i] + mx - 1) // mx ans += k - 1 mx = nums[i] // k return ans(code-box)
