Hard

题目描述

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

例如，nums = [5,6,7]。在一次操作中，我们可以将 nums[1] 替换为 2 和 4，数组变为 [5,2,4,7]。

返回使数组变为非递减顺序所需的最少操作次数。

示例 1：

输入：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。

示例 2：

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

约束条件：

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

解题思路

这道题的核心思想是从右向左贪心处理，因为最后一个元素不需要操作，它可以作为前面元素的上界参考。

主要思路：

  1. 从右向左遍历：最右边的元素保持不变，它将作为左边元素能达到的最大值的约束。

  2. 贪心策略：对于当前元素 nums[i]，如果它大于右边的约束值 bound，需要将其拆分。拆分的策略是：

    • 计算需要拆分成多少个部分：parts = (nums[i] + bound - 1) / bound（向上取整）
    • 操作次数增加 parts - 1
    • 更新新的约束值：bound = nums[i] / parts（拆分后最小值作为新约束）

  3. 为什么这样是最优的：

    • 我们希望拆分后的最小值尽可能大，这样对左边元素的约束最宽松
    • 同时要保证拆分后的最大值不超过右边的约束
    • 均匀拆分能使最小值最大化

  4. 数学细节：

    • 将 x 拆分成 k 个数，和为 x，要使最小值最大，应该尽量均匀分配
    • 最小值为 x // k，最大值为 x // k + (1 if x % k != 0 else 0)

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

代码实现

class Solution {
public:
    long long minimumReplacement(vector<int>& nums) {
        int n = nums.size();
        long long operations = 0;
        int bound = nums[n-1];
        
        for (int i = n-2; i >= 0; i--) {
            if (nums[i] <= bound) {
                bound = nums[i];
            } else {
                int parts = (nums[i] + bound - 1) / bound;
                operations += parts - 1;
                bound = nums[i] / parts;
            }
        }
        
        return operations;
    }
};

class Solution:
    def minimumReplacement(self, nums: List[int]) -> int:
        n = len(nums)
        operations = 0
        bound = nums[-1]
        
        for i in range(n-2, -1, -1):
            if nums[i] <= bound:
                bound = nums[i]
            else:
                parts = (nums[i] + bound - 1) // bound
                operations += parts - 1
                bound = nums[i] // parts
        
        return operations

public class Solution {
    public long MinimumReplacement(int[] nums) {
        int n = nums.Length;
        long operations = 0;
        int bound = nums[n-1];
        
        for (int i = n-2; i >= 0; i--) {
            if (nums[i] <= bound) {
                bound = nums[i];
            } else {
                int parts = (nums[i] + bound - 1) / bound;
                operations += parts - 1;
                bound = nums[i] / parts;
            }
        }
        
        return operations;
    }
}

/**
 * @param {number[]} nums
 * @return {number}
 */
var minimumReplacement = function(nums) {
    const n = nums.length;
    let operations = 0;
    let bound = nums[n-1];
    
    for (let i = n-2; i >= 0; i--) {
        if (nums[i] <= bound) {
            bound = nums[i];
        } else {
            const parts = Math.ceil(nums[i] / bound);
            operations += parts - 1;
            bound = Math.floor(nums[i] / parts);
        }
    }
    
    return operations;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(n)
空间复杂度O(1)

相关题目