1713. 得到子序列的最少操作次数 力扣（困难） 最长公共子序列->最长上升子序列 lower(vector) 得迭代器

题目描述：

给你一个数组 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] 不是子序列。

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

题解：https://leetcode-cn.com/problems/minimum-operations-to-make-a-subsequence/solution/gong-shui-san-xie-noxiang-xin-ke-xue-xi-oj7yu/

此题最好，掌握以下最长上升子序列的二分解法！！！！

其中一个经典的性质就是：当其中一个数组元素各不相同时，最长公共子序列问题（LCS）可以转换为最长上升子序列问题（LIS）进行求解。同时最长上升子序列问题（LIS）存在使用「维护单调序列 + 二分」的贪心解法，复杂度为 O(nlogn)。

    核心：一个数组维护长度为len的，末尾最小元素。eg.  1,2,4,8  长度为4， 如果出现了5， 变成1,2,4,5。降低门槛！！！

代码学习点： lower_bound（vector）  ，参考：本博客另一题

代码：

class Solution {
public:
    int minOperations(vector<int>& target, vector<int>& arr) {
     map<int,int> mp;
     for(int i=0;i<target.size();i++)    mp[target[i]]=i+1;   // 赋予索引
     vector<int> f;  //  f[len]=x 表示，代表上升子序列长度为 len 的上升子序列的「最小结尾元素」为 x。（目的：为后面每个元素计算它的最长上升子序列铺路）
     for(int i=0;i<arr.size();i++)
     if(mp.find(arr[i])!=mp.end())
     {
         auto j=lower_bound(f.begin(),f.end(),mp[arr[i]]);  //这就是log(n)的原因
         if (j==f.end()) f.push_back(mp[arr[i]]); //  如果没有比当前元素大的值，直接可以增加长度1
         else  *j=mp[arr[i]];  // 如果有比向前元素较大的值，替换，维护长度相同，但元素值更小。
     }
     return target.size()-f.size();
    }
};