题目描述

给你一个下标从 0 开始的整数数组 nums。每次操作中，你可以将数组中任何一个元素替换为 任意两个 和为该元素的数字。

• 比方说，nums = [5,6,7]。一次操作中，我们可以将 nums[1] 替换成 2 和 4，将 nums 转变成 [5,2,4,7]。

请你执行上述操作，将数组变成元素按 非递减 顺序排列的数组，并返回所需的最少操作次数。

样例

输入：nums = [3,9,3]
输出：2
解释：以下是将数组变成非递减顺序的步骤：
- [3,9,3]，将 9 变成 3 和 6，得到数组 [3,3,6,3]。
- [3,3,6,3]，将 6 变成 3 和 3，得到数组 [3,3,3,3,3]。 
总共需要 2 步将数组变成非递减有序，所以我们返回 2。

输入：nums = [1,2,3,4,5]
输出：0
解释：数组已经是非递减顺序，所以我们返回 0。

限制

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9

算法

(贪心) $O(n)$

1. 注意到，数字只会越拆分越小，所以需要对较大的数字下手。
2. 从数组末尾开始往前寻找，找到第一个非递减顺序的位置 $p$，满足 $p > 0$ 且 $nums(p) < nums(p - 1)$。
3. 如果 $p$ 不存在，则说明数组已经是非递减顺序，直接返回。
4. 定义最大可保留的数字为 $target$，初始化 $target := nums(p)$。从 $p - 1$ 开始倒序拆分。
5. 如果 $nums(i) \text{ mod } target = 0$，则说明 $nums(i)$ 可以完全拆分为若干个 $target$，则答案增加 $nums(i) / target - 1$，并且 $target$ 保持不变。
6. 否则，拆分的最少次数就是 $c := nums(i) / target$ 次，但拆分为 $c + 1$ 个数字后需要尽可能的让最小的数字最大（作为下一次拆分的 $target$），此时最小数字的最大可能值为 $target := nums(i) / (c + 1)$。
7. 注意到，两种情况可以合到一起处理，即直接从数组末尾开始计算。

时间复杂度

• 遍历数组一次，故时间复杂度为 $O(n)$。

空间复杂度

• 仅需要常数的额外空间。

C++ 代码

#define LL long long

class Solution {
public:
    LL minimumReplacement(vector<int>& nums) {
        const int n = nums.size();

        LL ans = 0;
        int target = nums[n - 1];

        for (int i = n - 2; i >= 0; i--) {
            int c = nums[i] / target;

            if (nums[i] % target == 0) {
                ans += c - 1;
            } else {
                ans += c;
                target = nums[i] / (c + 1);
            }
        }

        return ans;
    }
};