【二分算法】1187：使数组严格递增

大家好，欢迎来到IT知识分享网。

涉及知识点

动态规划 二分查找

LeetCode1187：使数组严格递增

分析

时间复杂度

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是降序。

处理思路

对于每个前值（前一个元素的值），有两种操作方式：

代码

核心代码

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; } }; 

测试用例

//CConsole::Out(res); 

}

优化

Add(pre, -1, 0); for (int i = 0; i < arr1.size(); i++) 

2023年1月旧版

扩展阅读

视频课程

如何你想快

相关下载

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境：

VS2022 C++17