题目描述

leetcode1187. 使数组严格递增

给你两个整数数组 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

 

题解——两种很直白好懂的dp方法

理解题意

简单来说，一步操作是使用arr2中的一个数替换arr1中的一个数。
很自然地，我们可以对arr1从头到尾进行这个过程，对每一个值进行操作（或者不操作），从而由部分有序构建全体有序。
考虑进行到arr1[i]时，此时0~i-1已经有序，此时我们面临两种选择：

  • 不进行替换，前提是arr1[i]>arr1[i-1](注意是替换后的arr1[i-1])，操作数不变。
  • 进行替换，就要考虑用哪个数来替换，此时采用贪心的思想：首先，这个数必须比arr1[i-1]大以保证有序，在这个前提下，越小越好，这也是很显然的。所以，我们希望找到arr2中比arr1[i-1]大的最小值进行替换，使用排序+二分查找，操作数+1。

需要指出，在已经递增的情况下，执行替换也可能更好，因为可以使末位变小。实际上，我们就是要在最后一个数更小和操作数更少之间进行取舍，也依此来定义状态。
有了这样的思路，可以开始设计dp了。

第一种dp——最后一个数固定时的最小操作数

根据上面的思路，定义dp[i][j]为：对于前i个数构成的递增序列，在最后一个数为j时的最小操作数。
状态转移方程：

转移方程比较丑，但是简单来说，对于每一个dp[i-1][j]，如果j<arr1[i]，则可以转移到dp[i][arr1[i]]并且操作数不变（不进行转化）；而对于每一个j，如果二分查找成功在arr2中找到k，那就可以转移到dp[i][k]，并且操作数+1。
因为状态转移只发生在相邻两个数组之间，可以优化掉一维，改用两个一维数组实现。
在代码实现上，由于最后一个数是不连续的，要用哈希表作为dp数组；dp[i]表示当前序列最后一个数为i时的最小操作数，我们从头到尾遍历arr1，并对上一个哈希表内的状态进行转移即可。
不同的值最多m+n个，因此这种方法的时间复杂度为O(n*(m+n)*logm)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int makeArrayIncreasing(vector<int>& arr1, vector<int>& arr2) {
        sort(arr2.begin(),arr2.end());//对arr2排序以进行二分查找
        unordered_map<int,int> dp;//dp数组
        dp[-1]=0;//迭代初始值
        for(int i=0;i<arr1.size();++i)//遍历arr1中的每个值，使得0~i有序
        {
            unordered_map<int,int> next;//下一个dp数组
            for(auto&p:dp)//遍历上层数组，进行状态转移
            {
                if(arr1[i]>p.first)//如果本来就有序了，可以不替换
                    next[arr1[i]]=next.count(arr1[i])?min(next[arr1[i]],p.second):p.second;
                auto iter=upper_bound(arr2.begin(),arr2.end(),p.first);//二分找到最优替换
                if(iter==arr2.end())//没找到，跳过
                    continue;
                next[*iter]=next.count(*iter)?min(next[*iter],p.second+1):p.second+1;
            }
            swap(dp,next);//滚动
        }
        int ans=INT_MAX;
        for(auto&p:dp)//遍历最后一个dp数组找到最优解
            ans=min(ans,p.second);
        return ans==INT_MAX?-1:ans;
    }
};

第二种dp——操作数固定时的最小末尾

前面说过，我们面临的是最后一个数更小和操作数更少之间的取舍，第一种方法是固定最后一个数，与之对称，我们也可以固定操作数。
直接省略外层数组，定义dp[i]为当前序列，在操作数为i时所能得到的最后一个数的最小值，转移方程如下：

代码实现上，从头到尾遍历arr1，对于每一个arr1[i]，遍历dp并进行转移，得到next。
细节：操作数最多为min(n,m)，所以我们设置一个lim作为上限，同时，在遍历到arr1[i]时，操作数也不会超过i+1，在遍历dp时进行控制即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int makeArrayIncreasing(vector<int>& arr1, vector<int>& arr2) {
        sort(arr2.begin(),arr2.end());
        int lim=min(arr1.size(),arr2.size());//操作数上限
        vector<int> dp(lim+1,-1);
        for(int i=0;i<arr1.size();++i)
        {
            vector<int> next(lim+1,INT_MAX);
            for(int j=0;j<=i&&j<lim;++j)//操作数为min(i+1,n,m)
            {
                if(arr1[i]>dp[j])//如果本来就有序了，可以不替换
                    next[j]=min(next[j],arr1[i]);
                auto iter=upper_bound(arr2.begin(),arr2.end(),dp[j]);
                if(iter==arr2.end())
                    continue;
                next[j+1]=min(next[j+1],*iter);
            }
            swap(dp,next);
        }
        for(int i=0;i<=lim;++i)//找到答案
            if(dp[i]!=INT_MAX)
                return i;
        return -1;
    }
};