题目如下

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

题目解析

简单来看会发现这道题目是求最长公共子序列，但是求最长公共子序列的时间复杂度会很高，其实我们可以将这个问题转化为最长上升子序列的解法。根据target中互不相同，我们知道每个数字对应的坐标唯一;
于是最长公共子序列等价于arr用target的坐标转换后构成最长的上升子序列.因为子序列的顺序不会发生改变，还是按照原来的顺序进行排列，我们只需要记录下标即可。代码如下：

class Solution:def minOperations(self, target: List[int], arr: List[int]) -> int:# 数字对应坐标idx_dict = {num: i for i, num in enumerate(target)}stack = []for num in arr:# 只有在target的数字才可能属于公共子序列if num in idx_dict:# 转换坐标idx = idx_dict[num]# 该坐标在当前栈中的位置i = bisect.bisect_left(stack, idx)# 如果在最后要加入元素，否则要修改该位置的元素# 跟一般的讲，i代表了目前这个idx在stack中的大小位置，# 在前面出现还比idx大的stack中的元素是无法和idx构成最长上升子序列的。# i左边的数比idx小，可以和idx构成上升子序列，(idx构成的长度就是i+1)# idx比i的值小，将i替换后可以方便后面构成更优的子序列(越小后面能加入的数越多)if i == len(stack):stack.append(0)stack[i] = idx0# 最终stack的长度就构成了最长上升子序列的长度，用减法即可得到本题答案return len(target) - len(stack)