这道题是 LeetCode 2366 题：将数组排序的最少替换次数。

题目理解

给定一个整数数组 nums，你可以进行任意次操作：

· 选择一个元素 nums[i]，将它替换为两个数 a 和 b，且 a + b = nums[i]
· 数组长度会增加 1

目标：使数组变成非递减排序，求最少操作次数。

解题思路

贪心 + 倒序处理

1. 从后往前处理：因为只能拆分（不能合并），后面的数会影响前面数的上限
2. 记录当前最大值：从右向左遍历，维护当前已处理部分的最小值（即上一个数拆分后的最大值不能超过它）
3. 计算拆分次数：
      当前数 x 要小于等于 prev（后一个数）
   · 如果 x <= prev，无需拆分，更新 prev = x
   · 如果 x > prev，需要拆分：
     · 最少拆成 k = ceil(x / prev) 份
     · 操作次数 = k - 1
     · 拆分后的第一个数（最左边）的最大可能值是 x / k（向下取整），作为新的 prev

代码实现

```java
public long minimumReplacement(int[] nums) {
    int n = nums.length;
    long operations = 0;
    int prev = nums[n - 1]; // 最后一个数不动
    
    for (int i = n - 2; i >= 0; i--) {
        int curr = nums[i];
        if (curr <= prev) {
            prev = curr;
        } else {
            // 需要拆分 curr
            // 计算最少拆分成多少份，使得每份 <= prev
            int parts = (curr + prev - 1) / prev; // 向上取整
            operations += parts - 1; // 拆分次数 = 份数 - 1
            // 更新 prev 为拆分后最左边那个数的最大值
            prev = curr / parts;
        }
    }
    
    return operations;
}
```

示例演示

```
示例 1: nums = [3, 9, 3]
从后往前：
- prev = 3
- i=1: curr=9 > 3
  parts = ceil(9/3) = 3
  ops += 2, prev = 9/3 = 3
- i=0: curr=3 <= 3, prev=3
结果：2

示例 2: nums = [1, 2, 3, 4, 5]
已排序，无需操作：0
```

复杂度分析

· 时间复杂度：O(n)，一次遍历
· 空间复杂度：O(1)，只使用常数额外空间