Question

2366. 将数组排序的最少替换次数

English Version

题目描述

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

• 比方说，nums = [5,6,7] 。一次操作中，我们可以将 nums[1] 替换成 2 和 4 ，将 nums 转变成 [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 <= 105
• 1 <= nums[i] <= 109

解法

方法一：贪心

我们观察发现，要使得数组 $nums$ 变成非递减有序，也即单调递增，那么数组后面的元素应该尽可能大，所以，将数组 $nums$ 的最后一个元素 $nums[n-1]$ 替换成多个更小的数是没有必要的。

也即是说，我们可以从后往前遍历数组 $nums$，并且维护当前的最大值 $mx$，初始时 $mx = nums[n-1]$。

• 若当前遍历到的元素 $nums[i] \leq mx$，此时不需要将 $nums[i]$ 进行替换，我们直接更新 $mx = nums[i]$ 即可。
• 否则，我们需要将 $nums[i]$ 替换成多个和为 $nums[i]$ 的数，这些数的最大值为 $mx$，总共替换成 $k=\left \lceil \frac{nums[i]}{mx} \right \rceil$ 个数，所以需要进行 $k-1$ 次操作，累加到答案中。这 $k$ 个数中，最小的数为 $\left \lfloor \frac{nums[i]}{k} \right \rfloor$，因此，我们更新 $mx = \left \lfloor \frac{nums[i]}{k} \right \rfloor$。

遍历结束，返回总的操作次数即可。

时间复杂度 $O(n)$，其中 $n$ 为数组 $nums$ 的长度。空间复杂度 $O(1)$。

class Solution:
  def minimumReplacement(self, nums: List[int]) -> int:
    ans = 0
    n = len(nums)
    mx = nums[-1]
    for i in range(n - 2, -1, -1):
      if nums[i] <= mx:
        mx = nums[i]
        continue
      k = (nums[i] + mx - 1) // mx
      ans += k - 1
      mx = nums[i] // k
    return ans

class Solution {
  public long minimumReplacement(int[] nums) {
    long ans = 0;
    int n = nums.length;
    int mx = nums[n - 1];
    for (int i = n - 2; i >= 0; --i) {
      if (nums[i] <= mx) {
        mx = nums[i];
        continue;
      }
      int k = (nums[i] + mx - 1) / mx;
      ans += k - 1;
      mx = nums[i] / k;
    }
    return ans;
  }
}

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

func minimumReplacement(nums []int) (ans int64) {
  n := len(nums)
  mx := nums[n-1]
  for i := n - 2; i >= 0; i-- {
    if nums[i] <= mx {
      mx = nums[i]
      continue
    }
    k := (nums[i] + mx - 1) / mx
    ans += int64(k - 1)
    mx = nums[i] / k
  }
  return
}

function minimumReplacement(nums: number[]): number {
  const n = nums.length;
  let mx = nums[n - 1];
  let ans = 0;
  for (let i = n - 2; i >= 0; --i) {
    if (nums[i] <= mx) {
      mx = nums[i];
      continue;
    }
    const k = Math.ceil(nums[i] / mx);
    ans += k - 1;
    mx = Math.floor(nums[i] / k);
  }
  return ans;
}

impl Solution {
  #[allow(dead_code)]
  pub fn minimum_replacement(nums: Vec<i32>) -> i64 {
    if nums.len() == 1 {
      return 0;
    }

    let n = nums.len();
    let mut max = *nums.last().unwrap();
    let mut ret = 0;

    for i in (0..=n - 2).rev() {
      if nums[i] <= max {
        max = nums[i];
        continue;
      }
      // Otherwise make the substitution
      let k = (nums[i] + max - 1) / max;
      ret += (k - 1) as i64;
      // Update the max value, which should be the minimum among the substitution
      max = nums[i] / k;
    }

    ret
  }
}