1187. Make Array Strictly Increasing

题目信息

题号:

1187

难度:

Hard

主题:

数组、动态规划、替换

原题:

LeetCode 1187

重点:

一次操作可把 arr1 的任意元素替换为 arr2 中任意值;求严格递增所需最少替换次数,不可行返回 -1

题目重述

给定整数数组 arr1 和 arr2。一次操作选择下标 i 和 j,把 arr1[i] 替换为 arr2[j]。可以执行任意多次操作,arr2 中的值不会因使用而被移除。

请返回使 arr1 满足 arr1[0] < arr1[1] < ... 所需的最少操作次数;若无法变成严格递增数组,返回 -1。

1 <= arr1.length, arr2.length <= 2000,0 <= arr1[i], arr2[i] <= 10^9。

自建示例

替换一个过大的中间值:

输入:arr1 = [1,5,3,6], arr2 = [2,4]
输出:1
解释:把 5 替换为 2,得到 [1,2,3,6],数组严格递增。

可选替换值无法修复下降序列:

输入:arr1 = [3,2,1], arr2 = [3]
输出:-1
解释:唯一可用值也是 3,无论替换哪些位置都无法得到三个严格递增的元素。