动态规划+二分查找
时间复杂度O(nlogn)
空间复杂度O(n)
1.将数组按照从小到大排序；
2.维护两个数组f,g;f[i]表示第i个信封能够嵌套的层数，g[i]表示嵌套层数为i的信封中最后一个信封宽度的最小值；g是单调递增的序列；
3.从前往后遍历数组，保证g数组中信封的长度小于当前信封；利用二分从g数组中查找宽度小于当前数组的最后一个嵌套信封，记其层数为x，当前信封能够嵌套的最大层数就是x+1。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param letters intvector<vector<>> 
     * @return int
     */
    int maxLetters(vector<vector<int> >& w) {
        // write code here
        sort(w.begin(), w.end());
        int n = w.size();
        vector<int> f(n, 0), g(1, 0);
        int ans = 0;
        for (int i = 0, j = 0; i < n; i ++) {
            while (w[j][0] != w[i][0]) {
                if (g.size() == f[j]) g.push_back(w[j][1]);
                else g[f[j]] = min(g[f[j]], w[j][1]);
                j ++;
            }
            int l = 0, r = g.size() - 1;
            while (l < r) {
                int m = l + r + 1 >> 1;
                if (w[i][1] > g[m]) l = m;
                else r = m - 1;
            }
            f[i] = r + 1;
            ans = max(ans, f[i]);
        }
        return ans;
    }
};

用例太少了，我提交的一个有错误的代码，居然也能过。😂

不符合时间复杂度要求 就当一种参考啦 留着自己复习用

function maxLetters( letters ) {
    // write code here
    let  len = letters.length
    if(!len) return 0
    letters.sort((a,b)=> a[0]=== b[0]? a[1]-b[1]:a[0]-b[0])
    const dp = new Array(len).fill(1)
    dp[0] = 1
    for(let i = 1;i<len;i++){
        for(let j = 0;j<i;j++){
            if(letters[i][1]>letters[j][1] && letters[i][0] !== letters[j][0]){
                dp[i] = Math.max(dp[i], dp[j]+1)
            }
    }
}
    return Math.max(...dp)
}

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param letters intvector<vector<>> 
     * @return int
     */
    static bool cmp(const vector<int> a,const vector<int> b)
    {
        if(a[0]==b[0])
            return a[1]>=b[1];//宽度相等时按照高度降序排列
        else
            return a[0]<b[0];//按照宽度升序排列
    }
    int LIS(vector<int> vec,int n)//经典的最长上升子序列问题，当然还可用二分优化
    {
        vector<int> dp(n,0);
        dp[0]=1;
        for(int i=1;i<n;i++)
        {
            for(int j=0;j<i;j++)
            {
                if(vec[i]>vec[j])
                    dp[i]=max(dp[i],dp[j]);
            }
            dp[i]++;
        }
        return *max_element(dp.begin(),dp.end());
    }
    int maxLetters(vector<vector<int> >& letters) {
        // write code here
        int n=letters.size();
        sort(letters.begin(),letters.end(),cmp);//排序
        vector<int> height;
        for(int i=0;i<n;i++)
        {
            height.push_back(letters[i][1]);
        }
        int res=LIS(height,n);//按照高度最长上升子序列
        return  res;
    }
};