1187. Make Array Strictly Increasing¶
题目信息¶
- 题号:
1187
- 难度:
Hard
- 主题:
数组、动态规划、替换
- 原题:
- 重点:
一次操作可把
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,无论替换哪些位置都无法得到三个严格递增的元素。