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