题目

——将数组排序的最少替换次数

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.

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 <= 105
• 1 <= nums[i] <= 109

思路

题目大意是说，给定数组nums，每次操作可以将任意数字拆分成和等于原数字的两个数字，求最小拆分次数，使得拆分后的数组不降序。

拿到题先看数据规模，nums量级10⁵，nums[i]量级10⁹，大概率是动规贪心了。

我们来看看有没有可复用的子问题。

首先我们知道，再不计次数的前提下，任意数组都可以拆成非降序。（可以拆成全数字1）e.g.[3,2,1] => [(1,1,1),(1,1),(1)]

其次，数组里任意一个数字，是否需要拆分，取决于它的后面是否有比它大的数字。

对于数组最后一个数字，最优策略是不拆分，因为如果拆分，可能导致其他数字需要拆分，这增加了全局的拆分次数。对于数组的倒数第二个数字，即nums[-2]，如果nums[-2]<=nums[-1]，满足非降序要求，反之则需要拆分。那么，如果需要拆分，应该拆几次&拆成多少呢？

我们知道，拆分某个数字，仍需要保证拆分后的数字是非降序的，同时，拆分后的第一个数字应该尽可能的大（这样才能让nums[0:-2]尽可能的不切分）。

举个例子，nums=[2,5,2]，对于5，我们有一下几种拆分方式。

不拆->[5]

拆1次->[2,3]

拆2次->[1,2,2]

拆3次->[1,1,1,2]

拆4次->[1,1,1,1,1]

观察可得，拆分次数越多，拆分后第一个数字就越小；同时，给定拆分次数的情况下，如果想让拆分后的第一个数字最大，最优策略是尽可能平均拆分。

拆分次数可以二分，也可以直接求。

待拆分数字n，将n拆成不降序的m份(n₁，n₂，…，n_m），且n_i<T，同时n₁最小

拆分次数m = ceil(n / T)，拆分后最小元素n₁=n // m

一通分析下来，我们发现这道题不仅有可重入的子问题，子问题的最优解就是全局最优解——我们得到了一个贪心解法。

代码

import math
class Solution(object):
    def minimumReplacement(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        
        ret = 0
        cur_n = nums[-1]
        for n in reversed(nums):
            if n <= cur_n:
                cur_n = n
                continue
            pieces = int(math.ceil(1.0 * n / cur_n))
            
            ret += pieces - 1
            cur_n = n // pieces
                
                
        return ret

AC，收工！

——此处是内容的分割线——

除非注明，否则均为广陌原创文章，转载必须以链接形式标明本文链接

本文链接：https://www.utopiafar.com/2022/08/09/leetcode-2366-minimum-replacements-to-sort-the-array/

码字不易，如果觉得内容有帮助，欢迎留言or点赞！