LeetCode 题解工作台
使数组严格递增
给你两个整数数组 arr1 和 arr2 ，返回使 arr1 严格递增所需要的最小「操作」数（可能为 0）。 每一步「操作」中，你可以分别从 arr1 和 arr2 中各选出一个索引，分别为 i 和 j ， 0 和 0 ，然后进行赋值运算 arr1[i] = arr2[j] 。 如果无法让 arr1…
4
题型
6
代码语言
3
相关题
当前训练重点
困难 · 状态·转移·动态规划
答案摘要
我们定义 表示将 转换为严格递增数组，且 不替换的最小操作数。因此，我们在 设置首尾两个哨兵 和 。最后一个数一定是不替换，因此 即为答案。我们初始化 ，其余 。 接下来我们对数组 进行排序并去重，方便进行二分查找。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给你两个整数数组 arr1 和 arr2，返回使 arr1 严格递增所需要的最小「操作」数（可能为 0）。
每一步「操作」中，你可以分别从 arr1 和 arr2 中各选出一个索引，分别为 i 和 j，0 <= i < arr1.length 和 0 <= j < arr2.length，然后进行赋值运算 arr1[i] = arr2[j]。
如果无法让 arr1 严格递增，请返回 -1。
示例 1：
输入：arr1 = [1,5,3,6,7], arr2 = [1,3,2,4] 输出：1 解释：用 2 来替换5，之后arr1 = [1, 2, 3, 6, 7]。
示例 2：
输入：arr1 = [1,5,3,6,7], arr2 = [4,3,1] 输出：2 解释：用 3 来替换5，然后用 4 来替换 3，得到arr1 = [1, 3, 4, 6, 7]。
示例 3：
输入：arr1 = [1,5,3,6,7], arr2 = [1,6,3,3]
输出：-1
解释：无法使 arr1 严格递增。
提示：
1 <= arr1.length, arr2.length <= 20000 <= arr1[i], arr2[i] <= 10^9
解题思路
方法一：动态规划
我们定义 表示将 转换为严格递增数组，且 不替换的最小操作数。因此，我们在 设置首尾两个哨兵 和 。最后一个数一定是不替换，因此 即为答案。我们初始化 ，其余 。
接下来我们对数组 进行排序并去重，方便进行二分查找。
对于 ，我们考虑 是否替换。如果 ，那么 可以从 转移而来，即 。然后，我们考虑 替换的情况，显然 应该替换成一个尽可能大的、且比 小的数字，我们在数组 中进行二分查找，找到第一个大于等于 的下标 。然后我们在 的范围内枚举替换的个数，如果满足 ，那么 可以从 转移而来，即 。
最后，如果 ，说明无法转换为严格递增数组，返回 ，否则返回 。
时间复杂度 ，空间复杂度 。其中 为 的长度。
class Solution:
def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
arr2.sort()
m = 0
for x in arr2:
if m == 0 or x != arr2[m - 1]:
arr2[m] = x
m += 1
arr2 = arr2[:m]
arr = [-inf] + arr1 + [inf]
n = len(arr)
f = [inf] * n
f[0] = 0
for i in range(1, n):
if arr[i - 1] < arr[i]:
f[i] = f[i - 1]
j = bisect_left(arr2, arr[i])
for k in range(1, min(i - 1, j) + 1):
if arr[i - k - 1] < arr2[j - k]:
f[i] = min(f[i], f[i - k - 1] + k)
return -1 if f[n - 1] >= inf else f[n - 1]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(m * n * log n) because for each element in arr1 (length m) you may consider all elements in arr2 (length n) with a binary search. Space complexity is O(n) for storing the current dynamic programming states corresponding to arr2 values after deduplication. |
| 空间 | O(n) |
面试官常问的追问
外企场景- question_mark
Checks understanding of dynamic programming state transitions for arrays.
- question_mark
Tests ability to optimize with binary search in sorted replacement arrays.
- question_mark
Evaluates handling of impossible cases and edge conditions in sequence transformations.
常见陷阱
外企场景- error
Ignoring the need to sort and deduplicate arr2, leading to redundant checks.
- error
Failing to properly track multiple states in dynamic programming, causing incorrect minimal operation counts.
- error
Assuming a solution exists for all inputs, without checking impossible cases.
进阶变体
外企场景- arrow_right_alt
Find minimum replacements to make arr1 non-decreasing instead of strictly increasing.
- arrow_right_alt
Allow replacement elements from arr2 only at even indices of arr1.
- arrow_right_alt
Count the number of different strictly increasing sequences achievable with minimal replacements.