题目描述
给你两个整数数组 arr1
和 arr2
,返回使 arr1
严格递增所需要的最小操作数(可能为 0)。
每一步操作中,你可以分别从 arr1
和 arr2
中各选出一个索引,分别为 i
和 j
,0 <= i < arr1.length
和 0 <= j < arr2.length
,然后进行赋值运算 arr1[i] = arr2[j]
。
如果无法让 arr1
严格递增,请返回 -1
。
样例
输入:arr1 = [1,5,3,6,7], arr2 = [1,3,2,4]
输出:1
解释:用 2 来替换 5,之后 arr1 = [1, 2, 3, 6, 7]。
输入:arr1 = [1,5,3,6,7], arr2 = [4,3,1]
输出:2
解释:用 3 来替换 5,然后用 4 来替换 3,得到 arr1 = [1, 3, 4, 6, 7]。
输入: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
算法
(动态规划) $O(m \log m + n^2 \log m)$
- 设 $f(i, j)$ 表示使前 $i$ 个数字严格递增,且经过了 $j$ 次的赋值运算,第 $i$ 位数字的最小值。
- 首先将 $arr_2$ 数组排序。
- 初始时 $f(0, 0) = arr_1(0)$,$f(0, 1) = arr_2(0)$。其余为正无穷。
- 转移时,如果 $arr_1(i) > f(i - 1, j)$,$f(i, j) = min(f(i, j), arr_1(i))$,即这一次不赋值。如果这一次赋值,则如果 $f(i - 1, j - 1)$ 不是正无穷时,在 $arr_2$ 里二分查找大于 $f(i - 1, j - 1)$ 最小的数字 $up$,令 $f(i, j) = min(f(i, j), up)$,若 $up$ 不存在则不转移。
- 最终答案为最小的 $j$,满足 $f(n - 1, j)$ 不是正无穷。
时间复杂度
- 排序需要 $O(m \log m)$ 的时间。
- 动态规划的状态数为 $O(n^2)$,转移需要 $O(\log m)$ 的时间。
- 故总时间复杂度为 $O(m \log m + n^2 \log m)$。
空间复杂度
- 需要额外 $O(n^2)$ 的空间记录状态。
C++ 代码
class Solution {
public:
int makeArrayIncreasing(vector<int>& arr1, vector<int>& arr2) {
int n = arr1.size();
sort(arr2.begin(), arr2.end());
vector<vector<int>> f(n, vector<int>(n + 1, INT_MAX));
f[0][0] = arr1[0];
f[0][1] = arr2[0];
for (int i = 1; i < n; i++)
for (int j = 0; j <= i + 1; j++) {
if (arr1[i] > f[i - 1][j])
f[i][j] = min(f[i][j], arr1[i]);
if (j > 0) {
if (f[i - 1][j - 1] < INT_MAX) {
auto up = upper_bound(arr2.begin(), arr2.end(), f[i - 1][j - 1]);
if (up != arr2.end())
f[i][j] = min(f[i][j], *up);
}
}
}
for (int i = 0; i <= n; i++)
if (f[n - 1][i] != INT_MAX)
return i;
return -1;
}
};
周赛最后一题呀 题解出的好快
是的呀,很赞
是怎么分析出这样设f(i,j)的?
这个是算是经验吧,DP 大部分经验得靠刷题
请问哪里有比较好的dp题库可以推荐么,难度和leetcode相仿就行。
老哥你后来有遇到比较好的题库可以推荐吗
算法提高课QWQ
好吧谢啦