<leetcode c++>1713. 得到子序列的最少操作次数

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

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

看到这个题目，我一下就想到了字符串里面求子序列用动态规划的场景，所以我毫不犹豫的用起来熟悉的dp[m][n]，然后因为没注意到数据范围，惨遭time exceed

class Solution {
public:
    int minOperations(vector<int>& target, vector<int>& arr) {
        int m = target.size(), n = arr.size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 1e6));
        dp[0][0] = 0;
        bool flag = false;
        for(int i = 1; i <= m; i++){
            dp[i][0] = i;
            if(target[i - 1] == arr[0]) flag = true;
            dp[i][1] = flag ? i - 1: i;
        }
        flag = false;
        for(int i = 1; i <= n; i++){
            dp[0][i] = 0;
            if(target[0] == arr[i - 1]) flag = true;
            dp[1][i] = flag ? 0 : 1;
            
        } 
        for(int i = 2; i <= m; i++){
            for(int j = 2; j <= n; j++){
                if(target[i - 1] == arr[j - 1]){
                    dp[i][j] = dp[i - 1][j - 1];
                }else{
                    dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1]);
                }
            }
        }
        return dp[m][n];
    }
};

在我的一番猛力思考与头脑风暴（1s后）后，我悄咪咪去看了一眼题解，啊，竟然是最长上升子序列，把在arr中出现的target中的元素对应的顺序下标存进一个新数组，然后这个数组的最长上升序列就是我们可以在arr中找到的最长target的子序列。

然鹅，我寻思求最长上升子序列不还是O(n^2)吗？竟然，竟然让我在评论区看到了O(nlogn)的解法！所以究竟是什么魔法！

用ans[i]存储长度为i+1的子序列的末尾元素值。

用nums中的数字去更新ans数组，把num插入到ans[l] < num <= ans[r]的地方，如果num比ans末尾元素大，就把maxl+1，最后maxl就是最长上升子序列长度

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n, 0);
        int maxl = 0;
        for(int& num : nums){
            int l = 0, r = maxl;
            while(l < r){
                int mid = (l + r) / 2;
                if(ans[mid] < num){
                    l = mid + 1;
                }else
                    r = mid;
            }
            ans[l] = num;
            if(l == maxl) ++maxl;
        }
        return maxl;
    }
};

所以这道题目的正解来了

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n, 0);
        int maxl = 0;
        for(int& num : nums){
            int l = 0, r = maxl;
            while(l < r){
                int mid = (l + r) / 2;
                if(ans[mid] < num){
                    l = mid + 1;
                }else
                    r = mid;
            }
            ans[l] = num;
            if(l == maxl) ++maxl;
        }
        return maxl;
    }
    int minOperations(vector<int>& target, vector<int>& arr) {
        int m = target.size(), n = arr.size();
        vector<int> nums;
        unordered_map<int, int> mp;
        for(int i = 0; i < m; i++) mp[target[i]] = i;
        for(int& num : arr){
            if(mp.find(num) != mp.end())nums.push_back(mp[num]);
        }
        return m - lengthOfLIS(nums);
    }
};