LeetCode 1713. 得到子序列的最少操作次数（最长上升子序DP nlogn）

示例 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^5
1 <= target[i], arr[i] <= 10^9
target 不包含任何重复元素。

class Solution {
public:
    int minOperations(vector<int>& target, vector<int>& arr) {
        unordered_map<int,int> num_idx;
        for(int i = 0; i < target.size(); ++i)
            num_idx[target[i]] = i;
        vector<int> arr_idx;
        for(auto a : arr)
            if(num_idx.find(a) != num_idx.end())
                arr_idx.push_back(num_idx[a]);//存的idx
                //转化成在 arr_idx 中找最长上升子序列
                
        // 数据量很大，不能用 n^2 解法，需要 nlgn 解法
        vector<int> dp;//存最长上升子序末尾最小的数
        dp.reserve(num_idx.size()+1);//设置容量，避免搬移
        for(int i = 0; i < arr_idx.size(); ++i)
        {
            int cur = arr_idx[i];
            auto pos = lower_bound(dp.begin(),dp.end(),cur);
            if(pos == dp.end())
                dp.push_back(cur);
            else
                *pos = cur;
        }
        return target.size()-dp.size();//最少操作次数
    }
};