问题描述

LCS问题就是最长公共子序列问题，即给定一个数组 target 和另一个数组 arr ，要求返回最长公共子序列的长度。特别地，当 target中没有重复的元素时，这个问题等价于求最长上升子序列问题，即LIS问题。

例题

LeetCode 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：

1
2
3

输入： target = [5,1,3], arr = [9,4,2,3,4]
输出： 2
解释： 你可以添加5和1，使得 arr 变为 [5,9,4,1,2,3,4]，target 为 arr 的子序列

示例 2：

1 2	输入： target = [6,4,8,1,3,2], arr = [4,7,6,2,3,8,6,1] 输出: 3

题解

首先，我们不难发现，最终需要返回的结果就是 target 数组的长度和两个数组的最长公共子序列的长度的差，即LCS问题。

一般上来说，使用动态规划解决LCS问题需要复杂度为 O(n*m) （定义dp[i][j] 为target 前 i 项和 arr 前 j 项的公共子序列长度）。

但是由于target 数组是无重复的，我们可以将这一问题转化为LIS问题。我们首先建立target 数组中的元素和下标的一一映射关系，存储在哈希表中。然后遍历 arr 数组，找到 arr 数组中全部与 target 重复的元素，并将其下标记录在一个新的数组 vec 中。这样，我们只要找到 vec 数组的最大升序子序列即可。

使用动态规划暴力解决LIS问题需要的复杂度为 O(n²) （定义 dp[i] 为以 vec[i] 结尾的最长上升子序列的长度，每次计算 dp[i] 需要遍历一次 dp[0] ~ dp[i-1] ，并判断 vec[i] 是否可以接在后面， dp[i] 是其中的最大值）。

而使用贪心法，我们可以将求解LIS问题的复杂度降低到 O(nlogn) 。我们可以维护一个贪心数组 g ，定义 g[i] 为长度为 i 的公共子序列的最小结尾元素。可以证明，g[i] 是单调递增的 ~~（但是我不会证）~~ 。因为我们是从左往右扫描 vec 数组的，所以越小的结尾元素能让越多的后续元素接上。我们只要保存最小的结尾元素，就可以保证找到最长的升序子序列（的长度）。

举个例子，对于 vec = [6,7,0,0,2,0,2,6,7] 来说：

将 6 加入到数组 g中。此时 g[1] = 6
将 7 与 g 的最后一个元素比较，发现 7 > 6 ，所以直接将 7 放入数组 g 中。此时 g[1] = 6 , g[2] = 7
将 0 与 g 的最后一个元素比较，发现 0 < 7 ，所以长度为 1 的子序列的最小结尾元素是 0，我们更新 g[1] 为 0 。此时 g[1] = 0 , g[2] = 7 。
将 0 与 g 的最后一个元素比较，发现 0 < 7 ，所以长度为 1 的子序列的最小结尾元素是 0，g 保持不变。此时 g[1] = 0 , g[2] = 7 。
将 2 与 g 的最后一个元素比较，发现 2 < 7 ，所以长度为 2 的子序列的最小结尾元素是 2，我们更新 g[2] 为 2 。此时 g[1] = 0 , g[2] = 2 。
将 0 与 g 的最后一个元素比较，发现 0 < 2 ，所以长度为 1 的子序列的最小结尾元素是 0，g 保持不变。此时 g[1] = 0 , g[2] = 2 。
将 2 与 g 的最后一个元素比较，发现 2 = 2 ，所以长度为 2 的子序列的最小结尾元素是 2，g保持不变。此时g[1] = 0 , g[2] = 2 。
将 6 与 g 的最后一个元素比较，发现 6 > 2 ，所以直接将 6 放入数组 g 中。此时 g[1] = 0 , g[2] = 2 , g[3] = 6 。
将 7 与 g 的最后一个元素比较，发现 7 > 6 ，所以直接将 7 放入数组 g 中。此时 g[1] = 0 , g[2] = 2 , g[3] = 6 , g[4] = 7 。
遍历完毕，此时数组 g 的长度为 4 ，说明 vec 的最长升序子序列的长度为 4 。

当扫描到的 vec[i] 小于数组 g 最后一个元素时，我们应该找到数组 g 中大于 vec[i] 的最小值，并更新这个值为 vec[i] 。由于数组 g 是单调递增的，所以我们可以使用二分查找的方法来找到待更新的值，以达到 O(logn) 的查找复杂度。

代码：

class Solution {
public:
    int minOperations(vector<int>& target, vector<int>& arr){
        //建立一个target元素和下标的映射
        unordered_map<int,int> map;
        for(int i=0;i<target.size();i++) map[target[i]]=i;
        //找到arr和target中的重复元素，并用下标表示。
        vector<int> vec;
        for(int i : arr){
            if(map.count(i)>0) vec.push_back(map[i]);
        }
        int n=vec.size();
        if(n==0) return target.size();//特殊处理，如果没有重复元素就直接返回。
        vector<int> dp;
        dp.push_back(vec[0]);//初始化。
        for(int i=1;i<n;i++){
            if(vec[i]>dp[dp.size()-1]) dp.push_back(vec[i]);
            else{
                //开始二分查找
                int l=0;
                int r=dp.size()-1;
                while(l<r){
                    int mid=(l+r)/2;
                    if(dp[mid]<vec[i]) l=mid+1;
                    else if(dp[mid]==vec[i]) l=r=mid;
                    else r=mid;
                }
                //找到第一个大于vec[i]的元素，其下标为l。
                dp[l]=vec[i];//数组中的最小末尾元素。
            }
        }
        return target.size()-dp.size();
    }
};

有的没的

小黄鸭调试法

小黄鸭调试法是软件工程中使用的调试代码方法之一。就是在程序的调试、纠错或测试过程中，耐心地向小黄鸭解释每一行程序的作用，以此来激发灵感。

将自己学会的东西记录在Blog里，在写博文的过程中就知道什么东西自己已经掌握了，什么东西自己还没搞懂。

启真湖边的小鸭鸭

环己三烯的冬眠舱

LCS问题和LIS问题