题目描述
这是 LeetCode 上的 1713. 得到子序列的最少操作次数 ，难度为 中等。
Tag : 「最长公共子序列」、「最长上升子序列」、「贪心」、「二分」
给你一个数组 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 <=
- 1 <= target[i], arr[i] <=
- target 不包含任何重复元素。
基本分析
为了方便，我们令 长度为 ， 长度为 ， 和 的最长公共子序列长度为 ，不难发现最终答案为 。
因此从题面来说，这是一道最长公共子序列问题（LCS）。
但朴素求解 LCS 问题复杂度为 ，使用状态定义「 为考虑 a 数组的前 个元素和 b 数组的前 个元素的最长公共子序列长度为多少」进行求解。
而本题的数据范围为 ，使用朴素求解 LCS 的做法必然超时。
一个很显眼的切入点是 数组元素各不相同，当 LCS 问题增加某些条件限制之后，会存在一些很有趣的性质。
其中一个经典的性质就是：当其中一个数组元素各不相同时，最长公共子序列问题（LCS）可以转换为最长上升子序列问题（LIS）进行求解。同时最长上升子序列问题（LIS）存在使用「维护单调序列 + 二分」的贪心解法，复杂度为 。
因此本题可以通过「抽象成 LCS 问题」->「利用 数组元素各不相同，转换为 LIS 问题」->「使用 LIS 的贪心解法」，做到 的复杂度。
基本方向确定后，我们证明一下第 步和第 步的合理性与正确性。
证明
1. 为何其中一个数组元素各不相同，LCS 问题可以转换为 LIS 问题？
本质是利用「当其中一个数组元素各不相同时，这时候每一个“公共子序列”都对应一个不重复元素数组的下标数组“上升子序列”，反之亦然」。
我们可以使用题目给定的两个数组（ 和 ）理解上面的话。
由于 元素各不相同，那么首先 元素和其对应下标，具有唯一的映射关系。
然后我们可以将重点放在两者的公共元素上（忽略非公共元素），每一个“公共子序列”自然对应了一个下标数组“上升子序列”，反之亦然。
注意：下图只画出了两个数组的某个片段，不要错误理解为两数组等长。
如果存在某个“公共子序列”，根据“子序列”的定义，那么对应下标序列必然递增，也就是对应了一个“上升子序列”。
反过来，对于下标数组的某个“上升子序列”，首先意味着元素在 出现过，并且出现顺序递增，符合“公共子序列”定义，即对应了一个“公共子序列”。
至此，我们将原问题 LCS 转换为了 LIS 问题。
2. 贪心求解 LIS 问题的正确性证明？
朴素的 LIS 问题求解，我们需要定义一个 数组代表以 为结尾的最长上升子序列的长度为多少。
对于某个 而言，我们需要往回检查 区间内，所有可以将 接到后面的位置 ，在所有的 中取最大值更新 。因此朴素的 LIS 问题复杂度是 的。
LIS 的贪心解法则是维护一个额外 数组， 代表上升子序列长度为 的上升子序列的「最小结尾元素」为 。
整理一下，我们总共有两个数组：
- 动规数组：与朴素 LIS 解法的动规数组含义一致。代表以为结尾的上升子序列的最大长度；
- 贪心数组：代表上升子序列长度为的上升子序列的「最小结尾元素」为。
由于我们计算 时，需要找到满足 ，同时取得最大 的位置 。
我们期望通过 数组代替线性遍历。
显然，如果 数组具有「单调递增」特性的话，我们可以通过「二分」找到符合 分割点 （下标最大），即利用 复杂度找到最佳转移位置。
我们可以很容易 通过反证法结合 数组的定义来证明 数组具有「单调递增」特性。
假设存在某个位置 和 ，且 ，不满足「单调递增」，即如下两种可能：
- ：这意味着某个值 既能作为长度 的上升子序列的最后一位，也能作为长度为 的上升子序列的最后一位。 根据我们对 数组的定义， 意味在所有长度为 上升子序列中「最小结尾元素」为 ，但同时由于 ，而且「上升子序列」必然是「严格单调」，因此我们可以通过删除长度为 的子序列后面的元素（调整出一个长度为 的子序列）来找到一个比 小的合法值。 也就是我们找到了一个长度为 的上升子序列，且最后一位元素必然严格小于 。因此 恒不成立；
- ：同理，如果存在一个长度为 的合法上升子序列的「最小结尾元素」为 的话，那么必然能够找到一个比 小的值来更新 。即 恒不成立。
根据全序关系，在证明 和 恒不成立后，可得 恒成立。
至此，我们证明了 数组具有单调性，从而证明了每一个 均与朴素 LIS 解法得到的值相同，即贪心解是正确的。
动态规划 + 贪心 + 二分
根据「基本分析 & 证明」，通过维护一个贪心数组 ，来更新动规数组 ，在求得「最长上升子序列」长度之后，利用「“公共子序列”和“上升子序列”」的一一对应关系，可以得出“最长公共子序列”长度，从而求解出答案。
Java 代码：
class Solution {public int minOperations(int[] t, int[] arr) {
int n = t.length, m = arr.length;
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < n; i++) {
map.put(t[i], i);
}
List<Integer> list = new ArrayList<>();
for (int i = 0; i < m; i++) {
int x = arr[i];
if (map.containsKey(x)) list.add(map.get(x));
}
int len = list.size();
int[] f = new int[len], g = new int[len + 1];
Arrays.fill(g, Integer.MAX_VALUE);
int max = 0;
for (int i = 0; i < len; i++) {
int l = 0, r = len;
while (l < r) {
int mid = l + r + 1 >> 1;
if (g[mid] < list.get(i)) l = mid;
else r = mid - 1;
}
int clen = r + 1;
f[i] = clen;
g[clen] = Math.min(g[clen], list.get(i));
max = Math.max(max, clen);
}
return n - max;
}
}
Python 3 代码：
class Solution:def minOperations(self, t: List[int], arr: List[int]) -> int:
n, m = len(t), len(arr)
map = {num:i for i,num in enumerate(t)}
lt = []
for i in range(m):
x = arr[i]
if x in map:
lt.append(map[x])
length = len(lt)
f, g = [0] * length, [inf] * (length + 1)
maximum = 0
for i in range(length):
l, r = 0, length
while l < r:
mid = l + r + 1 >> 1
if g[mid] < lt[i]:
l = mid
else:
r = mid - 1
clen = r + 1
f[i] = clen
g[clen] = min(g[clen], lt[i])
maximum = max(maximum, clen)
return n - maximum
- 时间复杂度：通过复杂度得到的下标映射关系；通过复杂度得到映射数组；贪心求解 LIS 的复杂度为。整体复杂度为
- 空间复杂度：
最后
这是我们「刷穿 LeetCode」系列文章的第 No.1713 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。