leetcode1713 得到子序列的最少操作次数

思路：

重新编号之后转化为LIS。

实现：

 1 class Solution
 2 {
 3 public:
 4     int LIS(vector<int>& nums)
 5     {
 6         int n = nums.size();
 7         vector<int> v(1, -1);
 8         for (int i = 0; i < n; i++)
 9         {
10             int p = lower_bound(v.begin(), v.end(), nums[i]) - v.begin() - 1;
11             if (p + 1 == v.size()) v.push_back(nums[i]);
12             else v[p + 1] = min(v[p + 1], nums[i]);
13         }
14         return v.size() - 1;
15     }
16     int minOperations(vector<int>& target, vector<int>& arr)
17     {
18         int n = target.size(), m = arr.size();
19         unordered_map<int, int> mp;
20         for (int i = 0; i < n; i++)
21         {
22             mp[target[i]] = i;
23         }
24         vector<int> v;
25         for (int i = 0; i < m; i++)
26         {
27             if (!mp.count(arr[i])) continue;
28             v.push_back(mp[arr[i]]);
29         }
30         return n - LIS(v);
31     }
32 };