题解 | #信封嵌套问题#

时间复杂度O(NlogN), 空间复杂度O(N)

[C++ 代码]

#include <algorithm>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param letters intvector<vector<>> 
     * @return int
     */
    int maxLetters(vector<vector<int> >& letters) {
        int n = letters.size();
        // 按长度从小到大排序，相等时按宽度从大到小排序
        sort(letters.begin(), letters.end(), [&](const auto& a, const auto& b){
            return a[0] < b[0] || (a[0]==b[0] && a[1] > b[1]);
        });
        // 求最长严格递增子序列的思路
        vector<int> temp;
        temp.emplace_back(letters[0][1]);
        for(int i=1; i<n; ++i){
            if(letters[i][1] > temp.back()) temp.emplace_back(letters[i][1]);
            else{
                auto it = lower_bound(temp.begin(), temp.end(), letters[i][1]);
                *it = letters[i][1];
            }
        }
        return temp.size();
    }
};