使数组严格递增

标签: 数组 二分查找 动态规划 排序

难度: Hard

给你两个整数数组 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 <= 2000
  • 0 <= arr1[i], arr2[i] <= 10^9

Submission

运行时间: 127 ms

内存: 16.6 MB

class Solution:
    def makeArrayIncreasing(self, arr1: List[int], b: List[int]) -> int:
        a = arr1 + [inf]  # 简化代码逻辑
        b = sorted(set(b))  # 去重+排序
        @cache  # 缓存装饰器，避免重复计算 dfs 的结果
        def dfs(i: int) -> int:
            # i=0 时不会继续递归，返回 1
            k = bisect_left(b, a[i])
            res = 0 if k >= i else -inf  # 替换 a[i] 左侧全部元素
            if i and a[i - 1] < a[i]:  # 无替换
                res = max(res, dfs(i - 1))
            for j in range(i - 2, max(i - k - 2, -1), -1):
                if b[k - (i - j - 1)] > a[j]:
                    # a[j+1] 到 a[i-1] 替换成 b[k-(i-j-1)] 到 b[k-1]
                    res = max(res, dfs(j))
            return res + 1  # 把 +1 移到这里，表示 a[i] 不替换
        ans = dfs(len(a) - 1)  # 注意 a 已经添加了一个元素，len(a)=n+1
        return -1 if ans < 0 else len(a) - ans

Explain

这个题解使用了动态规划和二分查找。具体思路是：对于 arr1 的每个位置 i，考虑是否替换 arr1[i] 以及替换成 arr2 中的哪个元素。通过递归函数 dfs(i) 来计算arr1[0:i+1] 变为严格递增序列所需的最小替换次数。 在 dfs(i) 中，首先用二分查找找到 arr2 中严格大于 arr1[i] 的最小元素的下标 k。然后比较两种可能性： 1. 不替换 arr1[i]，只需 arr1[i-1] < arr1[i]，这种情况下替换次数为 dfs(i-1)。 2. 替换 arr1[i]，需要枚举替换的起始位置 j，满足 j < i-1 且 arr2[k-(i-j-1)] > arr1[j]，即用arr2[k-(i-j-1):k] 替换 arr1[j+1:i]，这种情况下替换次数为 dfs(j)+i-j-1。最后取所有可能性的最小值。 通过添加 @cache 装饰器来缓存dfs结果，避免重复计算。如果最终 dfs(n) < n（n为数组长度），则说明可以得到严格递增序列，返回替换次数 n-dfs(n)，否则返回-1。

时间复杂度: O(n * min(n, m) * log m)

空间复杂度: O(n + m)

class Solution:
    def makeArrayIncreasing(self, arr1: List[int], b: List[int]) -> int:
        a = arr1 + [inf]  # 简化代码逻辑
        b = sorted(set(b))  # 去重+排序
        
        @cache  # 缓存装饰器，避免重复计算 dfs 的结果
        def dfs(i: int) -> int:
            # i=0 时不会继续递归，返回 1
            k = bisect_left(b, a[i])  # 二分查找 b 中严格大于 a[i] 的最小元素下标 k
            res = 0 if k >= i else -inf  # 如果 k >= i，则替换 a[i] 左侧全部元素
            if i and a[i - 1] < a[i]:  # 情况1：无替换
                res = max(res, dfs(i - 1))  # 递归计算 dfs(i-1)
            for j in range(i - 2, max(i - k - 2, -1), -1):  # 枚举替换的起始位置 j
                if b[k - (i - j - 1)] > a[j]:  # 如果满足替换条件
                    # a[j+1] 到 a[i-1] 替换成 b[k-(i-j-1)] 到 b[k-1]
                    res = max(res, dfs(j))  # 递归计算 dfs(j)
            return res + 1  # 把 +1 移到这里，表示 a[i] 不替换
        
        ans = dfs(len(a) - 1)  # 计算 dfs(n)，注意 a 已经添加了一个元素，len(a)=n+1
        return -1 if ans < 0 else len(a) - ans  # 如果 dfs(n) < n，则可以得到严格递增序列，返回替换次数，否则返回 -1

Explore

在动态规划中考虑不替换和替换当前元素两种情况，是为了覆盖所有可能的操作以确保找到最优解。这种分类使问题分解为更小、更可管理的子问题。不替换时，问题简化为前一个元素的状态；替换时，则考虑通过替换达到递增顺序的可能性。这样做可以确保无论数组当前的状态如何，都能评估所有可能的操作，从而找到使整个数组严格递增的最小替换次数。

使用二分查找来确定arr2中严格大于arr1[i]的最小元素可以显著提高算法效率。二分查找是一种高效的搜索方法，其时间复杂度为O(log n)，远快于线性搜索的O(n)。在动态规划的每个步骤中，都需要确定一个适合替换的最小元素，二分查找可以快速定位这个元素，从而减少每次递归调用的计算量，提高整体算法的执行速度。

这样的条件设置是为了确保替换操作能使数组部分段成为严格递增序列。条件j小于i-1是为了避免在同一位置重复替换，同时确保有足够的元素可以进行替换。条件arr2[k-(i-j-1)] > arr1[j]是为了确保替换后的序列在j处能维持严格递增，即替换的起点元素必须大于arr1中当前考虑的替换起始位置的元素，这是保持序列严格递增的关键条件。

在算法实现中，应该添加特定的边界条件检查来处理arr1或arr2为空的情况。如果arr1为空，理论上不需要任何替换，可以直接返回0。如果arr2为空，则无法进行任何替换操作，应检查arr1是否已经是严格递增的，如果是，则返回0；如果不是，则返回-1表示无法通过替换达到严格递增。这样的边界条件处理确保了算法在所有输入情况下都能给出正确的结果。