涉及知识点
动态规划 二分查找
题目
给你两个整数数组 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
分析
时间复杂度
O(nnlogn)。两层循环，第一层枚举结尾O(n)，第二层枚举前值O(n)，寻找第一个大于nums[i]的值O(logn)。
注意
arr2中的值可以重复取，所以arr2中重复的值可以删除。直接用有序集合记录就可以了。dp和pre的key都是记录前值，value记录操作次数。如果preValue0<=preValue1且iNum0<=iNum1，那preValue1被淘汰。能选择preValue1则一定能选择preValue0，而iNum0更小。淘汰后，dp和pre的key是升序，value是降序。
处理思路
对于每个前值（前一个元素的值），有两种操作方式：
| 如果前者<当前值 | 不替换 |
| setHas中存在大于前值的数 | 用符合条件的最小值替换 |
代码
核心代码
class Solution { public: int makeArrayIncreasing(vector<int>& arr1, vector<int>& arr2) { std::set<int> setHas(arr2.begin(), arr2.end()); auto Add = [](map<int, int>&dp,int iValue, int iNum) { //如果iValue和iNum都大，则被淘汰。淘汰后，iVaule升序，iNum降序 auto it = dp.upper_bound(iValue); if ((dp.begin() != it) && (std::prev(it)->second <= iNum)) { return;//被淘汰 } auto ij = it; for (; (dp.end() != ij) && (ij->second >= iNum); ++ij); dp.erase(it, ij); dp[iValue] = iNum; }; map<int, int> pre; Add(pre, arr1.front(), 0); Add(pre, *setHas.begin(), 1); for (int i = 1; i < arr1.size(); i++) { map<int, int> dp; for (const auto& [preValue, iNum] : pre) { if (preValue < arr1[i]) { //不换 Add(dp,arr1[i], iNum); } auto it = setHas.upper_bound(preValue); if (setHas.end()!= it ) { //换 Add(dp,*it, iNum + 1); } } dp.swap(pre); } return pre.empty() ? -1 : pre.rbegin()->second; } };
测试用例
template void Assert(const T& t1, const T& t2) { assert(t1 == t2); } template void Assert(const vector& v1, const vector& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { Assert(v1[i], v2[i]); } } int main() { vector arr1, arr2; int res; { Solution slu; arr1 = { 1, 5, 3, 6, 7 }, arr2 = { 1, 3, 2, 4 }; res = slu.makeArrayIncreasing(arr1, arr2); Assert(1, res); } { Solution slu; arr1 = { 1,5,3,6,7 }, arr2 = { 4,3,1 }; res = slu.makeArrayIncreasing(arr1, arr2); Assert(2, res); } { Solution slu; arr1 = { 1,5,3,6,7 }, arr2 = { 1,6,3,3 }; res = slu.makeArrayIncreasing(arr1, arr2); Assert(-1, res); } { Solution slu; arr1 = { 19, 18, 7, 4, 11, 8, 3, 10, 5, 8, 13 }, arr2 = { 13, 16, 9, 14, 3, 12, 15, 4, 21, 18, 1, 8, 17, 0, 3, 18 }; res = slu.makeArrayIncreasing(arr1, arr2); Assert(9, res); }
//CConsole::Out(res);
}
优化
Add(pre, -1, 0); for (int i = 0; i < arr1.size(); i++)
可以修改初始状态：
前值比任何数都小，操作次数0。从0开始循环。
2023年1月旧版
class Solution { public: int makeArrayIncreasing(vector& arr1, vector& arr2) { std::set set2; std::copy(arr2.begin(), arr2.end(), std::inserter(set2, set2.begin())); std::vector canSel; std::copy(set2.begin(), set2.end(), std::back_inserter(canSel)); std::unordered_map<int, int> mValueIndex; for (int i = 0; i + 1 < canSel.size(); i++) { mValueIndex[canSel[i]] = i + 1; } for (int i = 0 ; i < arr1.size(); i++) { int index = std::upper_bound(canSel.begin(), canSel.end(), arr1[i]) - canSel.begin(); if (index < canSel.size()) { mValueIndex[arr1[i]] = index; } } mValueIndex[-1] = 0; vector pre(arr1.size() + 1, INT_MAX); pre[0] = -1;//操作0次后，可以选择canSel[0]; for (int index1 = 0; index1 < arr1.size(); index1++) { const auto& data = arr1[index1]; std::vector dp(arr1.size() + 1, INT_MAX); for (int i = 0; i < pre.size(); i++) { const int iValue = pre[i]; if (INT_MAX == iValue) { continue; } if (mValueIndex.count(iValue)) { const int iNewValue = canSel[mValueIndex[iValue]]; dp[i + 1] = min(dp[i + 1], iNewValue); } if (data > iValue) { dp[i] = min(dp[i], data); } } pre.swap(dp); } for (int i = 0; i < pre.size(); i++) { if (INT_MAX != pre[i]) { return i; } } return -1; } };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法，请下载《闻缺陷则喜算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 洒家想对大家说的话 |
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 墨家名称的来源：有所得以墨记之。 |
| 如果程序是一条龙，那算法就是他的是睛 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境：
VS2022 C++17
