LeetCode-354.俄罗斯套娃信封问题

题目大意

给n个点，求

$$x_1 > x_0 \&\& y_1>y_0$$

的最大的链，n方的做法有很多，这里说nlogn的做法

先给x排序，然后如果第一维度相同第二维度倒序排序，然后球LIS即可

代码实现

class Solution {
    int arr[101001];
    vector<int>v;
    int getLIS(){
        for(int i=0;i<101001;i++)arr[i]=1e9+10;
        int l = 0;
        arr[0]=0;
        for(int i=0;i<v.size();i++){
            if(v[i]>arr[l])arr[++l]=v[i];
            else {
                int pos = lower_bound(arr + 1, arr + l + 1, v[i]) - arr;
                arr[pos]=v[i];
            }
        }
        return l;
    }
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        sort(envelopes.begin(),envelopes.end(),[](const vector<int>& a,const vector<int>& b){
            return a[0]<b[0]||(a[0]==b[0]&&a[1]>b[1]);});
        for(int i=0;i<envelopes.size();i++){
            v.push_back(envelopes[i][1]);
        }
        return getLIS();

    }
};