leetcode 2366. Minimum Replacements to Sort the Array（数组排序的最少替换数）

数组nums中的元素nums[ i ] 可以替换为任意两个数a, b, 前提是a+b = nums[ i ].
把数组nums变为升序（可以有相等）数组需要多少次替换。

思路：

排序数组是左边的元素<=右边元素，以右边元素为边界。
所以从右到左遍历数组，最右边的元素不需要处理。

拆分的时候最好是平均分，像10，最好拆成5和5，11就拆成5和6，
这样可以确保再往左遍历时，右边的元素尽可能的大，以减少拆分次数。
比如[5,10,8], 10最好拆成5和5，得到[5,5,5,8], 那么只需要拆一次，
如果把10拆成2和8，得到[5,2,8,8]， 那么最左边的元素5又要拆2次。

拆分出来的最小的数字（最左边的数字）就是下一元素的右边界。

假如右边界的数字为right, 那么拆分次数为cnt = (nums[ i ] - 1) / right,
其中最小的数字为nums[i] / (cnt + 1), 更新right为这个数。

如果nums[ i ]本身就<=right, 直接把right更新为nums[i], 进入下一遍历。

注意数值的范围，结果要用long型。

    public long minimumReplacement(int[] nums) {
       int n = nums.length;
       int right = nums[n-1];
       long res = 0;

       for(int i = n-2; i >= 0; i--) {
           if(nums[i] > right) {
               int splitCnt = (nums[i] - 1) / right;
               right = nums[i] / (splitCnt + 1);
               res += splitCnt;
           } else {
               right = nums[i];
           }
       }
       return res;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16