题目
给你一个数组 target ，包含若干 互不相同 的整数，以及另一个整数数组 arr ，arr 可能 包含重复元素。
每一次操作中，你可以在 arr 的任意位置插入任一整数。比方说，如果 arr = [1,4,1,2] ，那么你可以在中间添加 3 得到 [1,4,3,1,2] 。你可以在数组最开始或最后面添加整数。
请你返回 最少 操作次数，使得 target 成为 arr 的一个子序列。
一个数组的 子序列 指的是删除原数组的某些元素（可能一个元素都不删除），同时不改变其余元素的相对顺序得到的数组。比方说，[2,7,4] 是 [4,2,3,7,2,1,4] 的子序列（加粗元素），但 [2,4,2] 不是子序列。
示例1
- 输入： target = [5,1,3], arr = [9,4,2,3,4]
- 输出： 2
- 解释： 你可以添加 5 和 1 ，使得 arr 变为 [5,9,4,1,2,3,4] ，target 为 arr 的子序列。
示例2
- 输入： target = [6,4,8,1,3,2], arr = [4,7,6,2,3,8,6,1]
- 输出： 3
数据范围
1 <= target.length, arr.length <= 10^51 <= target[i], arr[i] <= 10^9target不包含任何重复元素。
分析
1 直观解法
首先，我们可以非常直接地想到两个数组的 最长公共子序列 的问题。
我们求出 target 和 arr 的最长公共子序列，然后在 arr 中，对这个序列进行元素的增添，即可使得 target 变成 arr 的子序列。于是答案应该是： target.size() - LongestCommonSequence.size() 。
然而，最长公共子序列所需的DP，时间复杂度是 O(n^2) ，根据题目的数据范围，会超时。
给出超时代码如下，可以通过 73/82 个用例。
class Solution {
public:
int minOperations(vector<int>& target, vector<int>& arr) {
// dp[a][b] target 从a开始,arr从b开始 得到的最长子序列
// target[a] == arr[b],则 dp[a][b] = dp[a - 1][b - 1] + 1
// target[a] != arr[b]。则 dp[a][b] = max(dp[a][b - 1], dp[a - 1][b], dp[a - 1][b - 1])
vector<vector<int>> dp(target.size() + 1, vector<int>(arr.size() + 1, 0));
for (int a = 0; a < target.size(); a++)
{
for (int b = 0; b < arr.size(); b++)
{
if (target[a] == arr[b])
{
dp[a][b] = (a == 0 || b == 0) ? 1 : dp[a - 1][b - 1] + 1;
}
else
{
if (a != 0 && b != 0)
{
dp[a][b] = max(
max(dp[a][b - 1], dp[a - 1][b]),
dp[a - 1][b - 1]
);
}
else if (a == 0 && b == 0)
{
dp[a][b] = 0;
}
else if (a == 0)
{
dp[a][b] = dp[a][b - 1];
}
else
{
dp[a][b] = dp[a - 1][b];
}
}
}
}
return target.size() - dp[target.size() - 1][arr.size() - 1];
}
};
2 问题转化
在最长公共子序列超时之后，就想不到其他的解法了……
翻阅题解发现，此前少考虑了一个条件：target 数组中的元素 互不相同 。
这是什么意思呢？我们似乎可以用某种映射来处理 target 数组中的元素啊。
我们发现，在 arr 数组中，可以用 下标 来代表 target 数组中的元素。
例如题目给出的示例2， target = [6,4,8,1,3,2] ， arr = [4,7,6,2,3,8,6,1] 。那么对于既出现在 target 数组中、又出现在 arr 数组中的元素 6,4,8,1,3,2 来说，我们直接在 arr 数组中将它们改写为这些元素在 target 数组中的下标，即使得 arr = [1,?,0,5,4,2,0,3] 。
我们要求这两个数组的最长公共子序列，这个子序列在 target 数组中是从前往后的，相当于是在转换后的 arr 数组中求得一个 最长递增 的序列。
对于像 7 这样只出现在 arr 数组中、不出现在 target 数组中的元素，它不可能出现在最长公共子序列中，也因此不应该放入最长递增序列的考虑范围，我们随便将它改为某个特定的值，在考虑最长递增序列的时候判断一下即可。
那么，我们应该如何求最长递增子序列呢？
2.1 最长递增子序列：DP
最长递增子序列的模板题可以看 300. 最长递增子序列 - 力扣（LeetCode） (leetcode-cn.com) 。
首先，最容易想到的办法肯定是DP了。我们使用数组 dp[i] 表示以第 i 个元素为结尾的最长递增子序列长度；那么，每考虑一位 i ，我们都要向前看 j = 0 ~ i-1 ，如果 nums[i] > nums[j] ，说明 nums[i] 可以直接加到这一序列上，得到的长度是 dp[j] + 1 ，所以 dp[i] = max(dp[j] + 1), j = 0~i-1且nums[i]>nums[j] 。
这一思想跟 难题本 | LeetCode面试题 08.13. 堆箱子 (gitee.io) 这篇文章中使用的DP是一样的。
使用这一思想做出来的模板是这样的：
// LeetCode 300. 最长递增子序列
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> dp(nums.size() + 2, 1);
dp[1] = 1;
for (int i = 2; i <= nums.size(); i++)
{
// cout << i << endl;
// dp[i] = dp[i - 1];
for (int last = i - 1; last >= 1; last--)
{
if (nums[i - 1] > nums[last - 1])
{
dp[i] = max(dp[i], dp[last] + 1);
}
}
// cout << i << " " << dp[i] << endl;
}
int res = INT_MIN;
for (int i = 1; i <= nums.size(); i++)
res = max(res, dp[i]);
return res;
}
};
问题是，这样做法复杂度还是 O(n^2) ，无法通过我们最初的问题。
2.2 最长递增子序列：贪心+二分
考虑一个简单的贪心，如果我们要使上升子序列尽可能的长，则我们需要让序列上升得尽可能慢，因此我们希望每次在上升子序列最后加上的那个数尽可能的小。
这样，我们使用一个数组 rec 来维护当前序列，如果一个数 nums[i] > rec.back() ，说明这个数可以直接放入序列中而不影响序列的递增性质，非常好；而如果 nums[i] < rec.back() ，那么我们应该去 rec 中找到 第一个大于 nums[i] 的数 ，使用 nums[i] 替换它。
上面的第二个条件看起来非常令人疑惑，实际上我们考虑这一情况的极端场景：整个 rec 数组中只有最后一个数比 nums[i] 更大。
例如 rec = [1,2,3,4,9] ， nums[i] = 5 ，那么，我们会自然地想到将 9 替换成 5 ，因为这样做能够维持序列的递增性，而且对于之后出现的 nums[i] 来说，继续加入这一递增序列的 可能性 更高。
更普遍地讲，我们将 rec 中第一个大于 nums[i] 的数替换成 nums[i] ，不会影响整个序列的递增性。假设被替换的数为 x ，有如下的两点：
rec数组中，x之前的所有数都小于nums[i]，因为x是第一个大于nums[i]的数；x之后的所有数本来就大于x，而x大于nums[i]，因此x之后的所有数都大于nums[i]；
可以看到，将 nums[i] 加入 rec 之后，对原有的递增性质没有任何影响；而对于之后出现的 nums[i] 来说，现在的 rec 数组已经是 尽可能小 的数组了，更容易加入到它们中间，维持递增。
这就是贪心的思想。而对于从 rec 中找到第一个大于 nums[i] 这一任务，我们可以利用 rec 的有序性，使用二分的办法进行查找。
这就有了如下的代码：
class Solution {
public:
int lengthOfLIS(vector<int>& nums) {
vector<int> rec;
int len = 1;
rec.push_back(nums[0]);
for (auto n : nums)
{
if (n > rec[len - 1])
{
rec.push_back(n);
len++;
}
else if (n < rec[len - 1])
{
int left = 0;
int right = len - 1;
int mid;
while (left <= right)
{
mid = (left + right) >> 1;
if (rec[mid] >= n)
right = mid - 1;
else
left = mid + 1;
}
rec[left] = n;
}
}
return len;
}
};
注意二分的边界，最终 left 应该指向第一个大于 nums[i] 的数，因此直接修改 rec[left] 即可。
3 本题终解
回到最初的问题来。
经过问题的转化，我们知道应该将 arr 数组中出现的 target 元素转化成它们在 target 数组中的下标，然后去求 arr 数组中的最长递增子序列的长度。
这就比较简单了。我们使用二分+贪心的办法，时间复杂度是 O(nlogn) ，应该可以AC。
class Solution {
public:
int minOperations(vector<int>& target, vector<int>& arr) {
map<int, int> mp;
for (int idx = 0; idx < target.size(); idx++)
{
mp[target[idx]] = idx; // target[idx] 出现的位置
}
for (int i = 0; i < arr.size(); i++)
{
if (mp.count(arr[i]))
{
arr[i] = mp[arr[i]];
}
else
{
arr[i] = INT_MIN;
}
}
vector<int> rec(1, INT_MIN);
int len = 0;
for (auto n : arr)
{
if (n > INT_MIN && n > rec[len])
{
rec.push_back(n);
len++;
}
else if (n > INT_MIN)
{
int left = 1;
int right = len;
while (left <= right)
{
int mid = (left + right) >> 1;
if (rec[mid] >= n)
right = mid - 1;
else
left = mid + 1;
}
rec[left] = n;
}
}
return target.size() - len;
}
};
参考资料
[1] 力扣官方题解.得到子序列的最少操作次数[EB/OL].2021-07-25
得到子序列的最少操作次数 - 得到子序列的最少操作次数 - 力扣（LeetCode） (leetcode-cn.com)
[2] 力扣官方题解.最长上升子序列[EB/OL].2020-03-13