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