题目描述

给你两个整数数组 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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/make-array-strictly-increasing
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

分析

本题难点在于如何定义动态规划状态以及状态转移方程
以往我们定义dp数组的值都是子问题的答案
但是在这里我们定义dp[i][j]表示arr1前i个元素经过j次变换后生成严格递增序列的末尾元素的最小值。
而答案是dp[arr1.length][j]存在的时候j的最小值。

对于arr1中的每一个数arr1[i]我们都有两种选择：替换和不替换
1、不替换的前提是arr1[i]>dp[i-1][j]，即在已经构建好的前i-1个元素递增序列尾加上当前元素仍是递增序列，此时dp[i][j]=arr1[i-1]
2、如果替换，则就要找到arr2中能够替换的最小值，也就是在arr2中>dp[i-1][j-1]的最小的值。替换后dp[i][j]=arr2[k]
最终取更小的那个赋值给dp[i][j]。

j的取值范围是0~min(i，arr2中可以用来替换的元素总个数），arr1的前i个元素最多可以被替换i次，最多能被arr2中不重复的元素来替换。

代码

class Solution {final int MaxV=Integer.MAX_VALUE;public int makeArrayIncreasing(int[] arr1, int[] arr2) {int m=arr1.length;Arrays.sort(arr2);List<Integer> list=new ArrayList<>();int f=-1;for(int x:arr2){if(x!=f){list.add(x);f=x;}}int n=list.size();int[][] dp=new int[m+1][Math.min(m,n)+1];for(int[] y:dp){Arrays.fill(y,MaxV);}dp[0][0]=-1;for(int i=1;i<m+1;i++){for(int j=0;j<=Math.min(i,n);j++){//不替换if(arr1[i-1]>dp[i-1][j]){dp[i][j]=arr1[i-1];}//进行替换，dp[i][j]=MaxV表示不存在这样的替换if(j>0 && dp[i-1][j-1]!=MaxV){int k=binarySearch(list,j-1,dp[i-1][j-1]);if(k!=n){//k=n，表示list中的最后一个元素（也就是最大值）都比dp[i-1][j-1]小，说明无法通过替换构成递增序列dp[i][j]=Math.min(dp[i][j],list.get(k));}}if(i==m && dp[i][j]!=MaxV){return j;}}}return -1;}//二分查找寻找target的插入位置也就是用来替换的元素索引public int binarySearch(List<Integer> list, int low, int target) {int high = list.size();while (low < high) {int mid = low + (high - low) / 2;if (list.get(mid) > target) {high = mid;} else {low = mid + 1;}}return low;}
}