## 题目地址(1713. 得到子序列的最少操作次数)

https://leetcode-cn.com/problems/minimum-operations-to-make-a-subsequence/

## 题目描述

```
给你一个数组 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 <= 105
1 <= target[i], arr[i] <= 109
target 不包含任何重复元素。
```

## 前置知识

- 动态规划
- LIS

## 公司

- 暂无

## 思路

这道题属于最长上升子序列的换皮题。关于最长上升子序列可以参考我之前写的文章[穿上衣服我就不认识你了？来聊聊最长上升子序列](https://lucifer.ren/blog/2020/06/20/LIS/)

具体的思路为：

1. 新建一个空的列表 B
2. 遍历 arr， 如果 arr 中的数字存在于 target 中，将其索引添加到列表 B 中
3. 求列表的最长上升子序列的长度（典型算法），这个长度实际上就是我们可以利用 arr 中的数所能组成的 **最长的** target 的子序列，换句话说，我们添加最少的数就可以构成 target。
4. 答案就是 target 的长度减去最长子序列的长度。

- 为了加快第 2 步的速度，可以建立 target 的反向索引方便能够在 $O(1)$ 时间根据 val 获取到索引。
- 由于这道题数据范围是 $10^5$，因此只能使用 $NlogN$ 的贪心才行。

> 关于为什么 10 ^ 5 就必须使用 $NlogN$ 甚至更优的算法我在[刷题技巧](https://lucifer.ren/blog/2020/12/21/shuati-silu3/)提过。更多复杂度速查可参考我的刷题插件，公众号《力扣加加》回复插件获取即可

## 关键点

- LIS

## 代码

```py
class Solution:
    def minOperations(self, target: List[int], A: List[int]) -> int:
        def LIS(A):
            d = []
            for a in A:
                i = bisect.bisect_left(d, a)
                if d and i < len(d):
                    d[i] = a
                else:
                    d.append(a)
            return len(d)
        B = []
        target = { t:i for i, t in enumerate(target)}
        for a in A:
            if a in target: B.append(target[a])
        return len(target) - LIS(B)
```

**复杂度分析**

- 时间复杂度：$O(max(BlogB, A))$。
- 空间复杂度：由于 target 大小大于 B 的大小，因此空间复杂度为 $O(target)$。

以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库：https://github.com/azl397985856/leetcode 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。

关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。

![](https://tva1.sinaimg.cn/large/007S8ZIlly1gfcuzagjalj30p00dwabs.jpg)
