安徽建站网站,360全景图制作,春雨app直播免费版下载,discuz网站建设教学视频文章目录1. 题目2. 解题1. 题目
给你两个整数数组 arr1 和 arr2#xff0c;返回使 arr1 严格递增所需要的最小「操作」数#xff08;可能为 0#xff09;。
每一步「操作」中#xff0c;你可以分别从 arr1 和 arr2 中各选出一个索引#xff0c;分别为 i 和 j#xff0c…
文章目录1. 题目2. 解题1. 题目
给你两个整数数组 arr1 和 arr2返回使 arr1 严格递增所需要的最小「操作」数可能为 0。
每一步「操作」中你可以分别从 arr1 和 arr2 中各选出一个索引分别为 i 和 j0 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.com/problems/make-array-strictly-increasing 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
参考题解 mike-meng
dp[i][j] 表示前 i 个元素替换 j 次最后一个元素的最小值
class Solution {
public:int makeArrayIncreasing(vectorint arr1, vectorint arr2) {sort(arr2.begin(), arr2.end());arr2.erase(unique(arr2.begin(), arr2.end()), arr2.end());// arr2 排序去重int n1 arr1.size(), n2 arr2.size();vectorvectorint dp(n11, vectorint(min(n1,n2)1, INT_MAX));// dp[i][j] 表示前 i 个元素替换 j 次最后一个元素的最小值dp[0][0] -1;for(int i 1; i n1; i) { for(int j 0; j min(n2,i); j){if(arr1[i-1] dp[i-1][j])//第 i 个数比 之前的最后一个元素大不用替换dp[i][j] min(dp[i][j], arr1[i-1]);if(j 0){auto it upper_bound(arr2.begin(), arr2.end(), dp[i-1][j-1]);// 前 i-1 个数替换了 j-1 次的最小尾部值 v找到arr2中比 v 大的最小值if(it ! arr2.end()){dp[i][j] min(dp[i][j], *it);}}if(i n1 dp[n1][j] ! INT_MAX)return j; // 遍历完了arr1}}return -1;}
};788 ms 36.3 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
