题目大意：
使数组严格递增
给你两个整数数组 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 <= 20000 <= arr1[i], arr2[i] <= 10^9
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1187
解题思路分析：
这是一道Hard难度的题目。难度在于我们不知道当前位置的数字是否该被替换。遇到这种题目我们就应该想到遍历所有的可能，即当前位置可以出现哪些种情况，然后再在这些分支中找到最优解。
由于题目要求数组需满足完全递增排序，因此，若当前数字小于等于前面的数字，那么一定需要替换，反之，则需要考虑替换或者不替换两种情况。如果不做替换的情况下，操作次数不会增加，当前位的操作次数就等于上一位的操作次数。若是发生替换，操作次数应该加一。接下来的关键就是找出当前数字可以替换为哪些数字？
理论上，在arr2数组中所有大于前一位的数字都是可以被选择的目标，考虑到之后的递增排序，这个目标值肯定越小越好，因此我们需要找到一个大于前一位数字的最小数作为替换目标。举个例子来说明，比如：
arr1 = [1,5,3,4] arr2 = [2,3,6]
假设当前位于arr1下标为1的位置，即数字5，因为5大于前一位的1，进而5本身是一个选择，此外，在arr2中大于前一位1的所有数字中的最小值2也是一个备选方案。这时，下标为1的选择有5和2两种情况，保持5不变需要的操作次数为0，选择2的操作次数为1。即：
// index为1时有2种选择 5 -> 0 // 选择5需要0次操作 2 -> 1 // 选择1需要1次操作
继续循环到下标为2的位置，即数字3。由于前一位有2种可能，如果前一位选择5的话，当前位的3大于它所以必须被替换掉，在arr2中大于5的最小值为6，因此6为一种方案，操作次数加一。另外一种情况，如果前一位选择2的话，当前位3符合条件，可以无需替换，操作次数不变仍为1（因为前一位选择2时已经执行了一次操作）。最后，我们还可以选择比前一位2大的最小数3作为一种替换方案，此时操作次数加一，应该为2。即：
// index为2时有3种选择 6 -> 1 // 前一位为5，选择6替换，当前1次操作，总共1次操作 3 -> 1 // 前一位为2，保持当前位，当前0次操作，总共1次操作 3 -> 2 // 前一位为2，选择3替换，当前1次操作，总共2次操作
接下来的循环同理，最后我们只要找到一个操作次数最少的值即是答案。
编码时，我们需要记录下当前位作出的选择，以及执行该选择需要执行操作的总次数。循环结束时找到最优解即可。
基本原理不难理解，但是有一点需要优化，否则执行效率会很低。比如前一位有N种选择，这N种选择的数字都小于当前位，那么当前位可以保持不变，操作次数也与前位相同，不过问题来了，这N种情况各自的操作次数不一定一致，我们应该选择哪一个？按照最优理论，答案肯定要选最少的那个。
看下完整代码：
public int makeArrayIncreasing(int[] arr1, int[] arr2) {
Arrays.sort(arr2); // 方便查找，将arr2排序
// 存储每一步的可能性
// int[0]为选择的数字，int[1]为该选择需要的操作次数
Queue<int[]> q = new LinkedList<>();
q.offer(new int[]{-1, 0}); // 初始化，假想第0位的前一位是-1。
for(int i=0;i<arr1.length;i++){ // 循环arr1
int size = q.size(); // 计算queue的大小
int minCount=Integer.MAX_VALUE; // 前一位所有选择的最小次数
while(size-->0){ // 当size变为0时，前一位的所有可能遍历完毕
int[] n = q.poll(); // 取前一位的一个选择
if(arr1[i] > n[0]){ // 如果当前位大于前一位。
// 先不急将当前选择加入queue中，找到最小的再说。
minCount = Math.min(minCount, n[1]);
}
// 选择一个比前一位大的最小数。
int min = findMin(arr2, n[0]);
if(min != -1){ // 如果找到了
// 将这个最小数加入到queue中
// 操作次数在前一位的基础上加一
q.offer(new int[]{min, n[1]+1});
}
} // 前一位所有情况循环结束
// 如果当前位可以保持不变，将最小次数加入到queue中
if(minCount!=Integer.MAX_VALUE){
q.offer(new int[]{arr1[i], minCount});
}
} // arr1循环结束
// 如果最后一位没有合法的选择方案，返回-1。
if(q.size()==0){
return -1;
}
int res=Integer.MAX_VALUE;
while(q.size()>0){ // 在queue中找到一个最小值最为返回结果
res = Math.min(res, q.poll()[1]);
}
return res;
}
Map<Integer, Integer> memo = new HashMap<>();
// 寻找一个大于min的最小值
int findMin(int[] arr2, int min){
if(memo.containsKey(min)){ // memo用于减少重复查询
return memo.get(min);
}
for(int i=0;i<arr2.length;i++){
if(arr2[i]<=min){
continue;
}else{
memo.put(min, arr2[i]);
return arr2[i];
}
}
memo.put(min, -1);
return -1;
}如果将findMin方法改为2分查找还可以大幅提高效率。时间原因，略过。
本解法运行时间92ms。
Runtime: 92 ms, faster than 60.15% of Java online submissions for Make Array Strictly Increasing.
Memory Usage: 39.4 MB, less than 100.00% of Java online submissions for Make Array Strictly Increasing.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-1187-make-array-strictly-increasing-解题思路分析/