每日一题做题记录，参考官方和三叶的题解

题目要求

思路一：贪心模拟

• 感觉是最好想到的思路，想的时候没有意识到这本质上是个贪心。
• 要使数对链最长，就尽可能保证数对中的后者较小，让后续数对有更多的选择：所以按后者进行排序，然后在此基础上判断链的关系（pairs[i][1]<pairs[i+1][0]pairs[i][1] < pairs[i+1][0]pairs[i][1]<pairs[i+1][0]）是否满足。

Java

class Solution {
    public int findLongestChain(int[][] pairs) {
        int preY = Integer.MIN_VALUE, res = 0;
        Arrays.sort(pairs, (a, b) -> a[1] - b[1]);
        for (int[] p : pairs) {
            if (preY < p[0]) {
                preY = p[1];
                res++;
            }
        }
        return res;
    }
}

• 时间复杂度：O(nlog⁡n)O(n\log n)O(nlogn)，排序的时间复杂度
• 空间复杂度：O(log⁡n)O(\log n)O(logn)，排序的空间复杂度

C++

class Solution {
public:
    int findLongestChain(vector<vector<int>>& pairs) {
        int preY = INT_MIN, res = 0;
        sort(pairs.begin(), pairs.end(), [](const vector<int> & a, const vector<int> & b) {
            return a[1] < b[1];
        });
        for (auto &p : pairs){
            if (preY < p[0]) {
                preY = p[1];
                res++;
            }
        }
        return res;
    }
};

• 时间复杂度：O(nlog⁡n)O(n\log n)O(nlogn)，排序的时间复杂度
• 空间复杂度：O(log⁡n)O(\log n)O(logn)，排序的空间复杂度

Rust

impl Solution {
    pub fn find_longest_chain(mut pairs: Vec<Vec<i32>>) -> i32 {
        pairs.sort_by(|a, b| a[1].cmp(&b[1]));
        pairs.iter().enumerate().fold((0, 1), |(i, res), (j, p)|
            if pairs[i][1] < p[0] {
                (j, res + 1)
            }
            else {
                (i, res)
            }).1
    }
}

• 时间复杂度：O(nlog⁡n)O(n\log n)O(nlogn)，排序的时间复杂度
• 空间复杂度：O(log⁡n)O(\log n)O(logn)，排序的空间复杂度

思路二：动态规划

• 是引入一个动态规划数组的模拟思路，在数组里不断更新最长能够达到的长度；
• 以前面的元素作为关键字进行排序，然后依次判断当前数对能否和其前面的数对构成链，可以的话就更新一下长度。

Java

class Solution {
    public int findLongestChain(int[][] pairs) {
        int n = pairs.length;
        Arrays.sort(pairs, (a, b) -> a[0] - b[0]);
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        for (int j = 1; j < n; j++) {
            for (int i = 0; i < j; i++) {
                if (pairs[i][1] < pairs[j][0]) // 合法
                    dp[j] = Math.max(dp[j], dp[i] + 1); // 长度加一
            }
        }
        return dp[n - 1];
    }
}

• 时间复杂度：O(n2)O(n^2)O(n2)，两个for循环套出来的复杂度完全cover了排序O(nlog⁡n)O(n\log n)O(nlogn)的复杂度。
• 空间复杂度：O(n)O(n)O(n)

C++

class Solution {
public:
    int findLongestChain(vector<vector<int>>& pairs) {
        int n = pairs.size();
        sort(pairs.begin(), pairs.end());
        int dp[n];
        memset(dp, 0, sizeof(dp));
        for (int j = 1; j < n; j++) {
            for (int i = 0; i < j; i++) {
                if (pairs[i][1] < pairs[j][0]) // 合法
                    dp[j] = max(dp[j], dp[i] + 1); // 长度加一
            }
        }
        return dp[n - 1] + 1;
    }
};

• 时间复杂度：O(n2)O(n^2)O(n2)，两个for循环套出来的复杂度完全cover了排序O(nlog⁡n)O(n\log n)O(nlogn)的复杂度。
• 空间复杂度：O(n)O(n)O(n)

思路三：贪心+二分

Java

class Solution {
    public int findLongestChain(int[][] pairs) {
        Arrays.sort(pairs, (a, b) -> a[0] - b[0]);
        List<Integer> resY = new ArrayList<Integer>();
        for (int[] p : pairs) {
            int x = p[0], y = p[1];
            if (resY.isEmpty() || x > resY.get(resY.size() - 1))
                resY.add(y);
            else {
                int idx = binSrch(resY, x); // 以x找位置
                resY.set(idx, Math.min(resY.get(idx), y)); // 判断y能否放入
            }
        }
        return resY.size();
    }

    // 二分查找
    public int binSrch(List<Integer> resY, int x) {
        int l = 0, r = resY.size() - 1;
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (resY.get(mid) >= x)
                r = mid;
            else
                l = mid + 1;
        }
        return l;
    }
}

• 时间复杂度：O(nlog⁡n)O(n\log n)O(nlogn)，二分需要O(n)O(n)O(n)次，所以二分的总复杂度和排序都是O(nlog⁡n)O(n\log n)O(nlogn)
• 空间复杂度：O(n)O(n)O(n)

C++

class Solution {
public:
    int findLongestChain(vector<vector<int>>& pairs) {
        sort(pairs.begin(), pairs.end());
        vector<int> resY;
        for (auto p : pairs) {
            int x = p[0], y = p[1];
            if (resY.empty() || x > resY.back())
                resY.emplace_back(y);
            else {
                int idx = lower_bound(resY.begin(), resY.end(), x) - resY.begin(); // 以x找位置
                resY[idx] = min(resY[idx], y); // 判断y是否能放入
            }
        }
        return resY.size();
    }
};

• 时间复杂度：O(nlog⁡n)O(n\log n)O(nlogn)，二分需要O(n)O(n)O(n)次，所以二分的总复杂度和排序都是O(nlog⁡n)O(n\log n)O(nlogn)
• 空间复杂度：O(n)O(n)O(n)

STL lower_bound()

• 学习参考链接
• 用于在指定区域内查找第一个不小于目标值的元素，也可自定义比较函数查找第一个不符合定义规则的元素。
• lower_bound(begin, end, target, comp)
  • beginbeginbegin和endendend都是正向迭代器，用于指定函数作用范围；
  • compcompcomp，可缺省，用于自定义比较规则，可以接收一个包含222个形参且返回值为bool的函数，其中第二个参数为目标值targettargettarget。
• 其底层基于二分查找实现，可用以替代需要二分的地方。
  • 其他类似的还有如下几个：

    方法	作用
    upper_bound()	查找第一个不大于目标值的元素
    equal_range()	查找所有等于目标值的元素
    binary_search()	查找是否包含目标元素

总结

无意中想到了最优解法，但后面的贪心和二分还是很有启发的，还找到了C++写二分的偷懒函数。

三叶姐姐还引申提到了LCS问题和LIS问题的解法，感觉规模有点大放一放后面有空补上学习。

对Rust不熟悉所以后两种就没有再花心力去撕，等系统学习之后认真把Rust作为题解的正式部分……官方能不能出个Rust嘤嘤嘤。

【因为方法好几个所以拖了几天才补上的题解】

欢迎指正与讨论！