目录

1187:使数组严格递增(2315 分)

力扣第 153 场周赛第 4 题

题目

给你两个整数数组 arr1arr2,返回使 arr1 严格递增所需要的最小「操作」数(可能为 0)。

每一步「操作」中,你可以分别从 arr1arr2 中各选出一个索引,分别为 ij0 <= i < arr1.length0 <= 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

相似问题:

分析

arr1 首位有两种情况:

  • 维持不变
  • 从 arr2 中选一个来替代,显然越小越好,故选择 min(arr2)

假设首位选择了 x,第二位也有两种情况:

  • 维持不变,注意必须满足 arr1[1] 大于 x
  • 从 arr2 中选一个来替代,显然越小越好,故选择比 x 大且最小的那个数

因此,只要保存上一位选择的数,即可递归求解:

  • 令 dfs(i,x) 代表 arr1[i-1] 选择了数 x 时,arr1[i:] 的最小操作数
  • 能维持不变时,转为子问题 dfs(i+1,arr1[i])
  • 能找到比 x 大且最小的数 arr2[j] 时,转为子问题 1+dfs(i+1,arr2[j])

为了快速找到 arr2[j],可以先将 arr2 排序,然后每次二分查找即可。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
def makeArrayIncreasing(self, arr1: List[int], arr2: List[int]) -> int:
	@cache
	def dfs(i, x):
		if i==len(arr1):
			return 0
		res = inf
		if arr1[i]>x:
			res = min(res, dfs(i+1, arr1[i]))
		j = bisect_right(arr2, x)
		if j<len(arr2):
			res = min(res, 1+dfs(i+1, arr2[j]))
		return res

	arr2.sort()
	res = dfs(0, -1)
	return res if res<inf else -1

724 ma