What is the main strategy for solving Minimum Replacements to Sort the Array?

The main strategy is to use a greedy approach, starting from the end of the array and performing the minimal number of operations to maintain the sorted order.

How do I avoid unnecessary operations in this problem?

By avoiding operations on the last element and ensuring each replacement maintains the non-decreasing order, you minimize unnecessary operations.

How does GhostInterview help with this problem?

GhostInterview helps by providing a clear explanation of the greedy approach, pointing out key observations, and breaking down the problem into manageable steps.

What is the time complexity of the solution for this problem?

The time complexity is typically O(n), where n is the length of the array, since we iterate through the array once in a greedy manner.

What should I keep in mind when solving Minimum Replacements to Sort the Array?

Focus on minimizing the number of operations by using a greedy strategy and validating that the array remains sorted after each replacement.

#2366

Hard

auto_awesome贪心·invariant

LeetCode 题解工作台

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

给你一个下标从 0 开始的整数数组 nums 。每次操作中，你可以将数组中任何一个元素替换为任意两个和为该元素的数字。比方说， nums = [5,6,7] 。一次操作中，我们可以将 nums[1] 替换成 2 和 4 ，将 nums 转变成 [5,2,4,7] 。请你执行上述操作，将数组变…

数组数学贪心

题目描述

给你一个下标从 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 <= 10⁵
1 <= nums[i] <= 10⁹

lightbulb

解题思路

方法一：贪心

我们观察发现，要使得数组 $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)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

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

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for the candidate's understanding of greedy algorithms and how they manage state during iteration.
question_mark
Pay attention to how the candidate avoids unnecessary operations, especially regarding the last element.
question_mark
Check whether the candidate correctly validates the invariant while implementing their solution.

warning

常见陷阱

外企场景

error
Not considering edge cases, like already sorted arrays or arrays where no replacements are needed.
error
Performing operations on the last element when it is unnecessary, leading to extra work.
error
Failing to manage the array state correctly during the greedy approach, causing invalid splits or incorrect results.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allowing more than two elements in a replacement, which changes the greedy strategy.
arrow_right_alt
Limiting the number of replacements allowed, requiring an optimization to minimize operations further.
arrow_right_alt
Introducing additional constraints, like maximum number of total elements, to affect the problem's scalability.

help

常见问题

外企场景

继续练习

#2358 分组的最大数量 #2195 向数组中追加 K 个整数 #2541 使数组中所有元素相等的最小操作数 II