Manjusaka

08-30 leetcode-2483

链接 2366. Minimum Replacements to Sort the Array

写题解第二天就是一个 Hard，麻了

题目：

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 replace nums[1] with 2 and 4 and convert nums to [5,2,4,7].
Return the minimum number of operations to make an array that is sorted in non-decreasing order.

这个题很好理解，以最小的拆分步数让数组成为一个非递减的有序数组，即 n[i]<=n[i+1]

题解

这题其实是个贪心的做法，我们可以这样想

1. 非递减，那么我们可以以最后一个数为基准 min_value 向前迭代
2. 如果往前一个数小于 min_value，那么不需要拆分，直接将 min_value 更新为当前值
3. 如果往前一个数大于 min_value, 那么我们需要进行拆分，同时要确保拆分出来的最小值最大
   1. 拆分步数为 k=current_value // min_value
   2. 新的 min_value 为 current_value // k，即根据步数均分

这样我们就可以得到一个 O(n) 的解法

class Solution:
    def minimumReplacement(self, nums: list[int]) -> int:
        result, min_value = 0, nums[-1]
        for item in nums[::-1]:
            k = (item - 1) // min_value
            result += k
            min_value = item // (k + 1)
        return result