Leetcode 354

题目要求

envelopes数组的元素为一个二维向量[wi, hi]，分别表示宽和高，规定i 可以套 j iff. wi > wj && hi > hj，求envelops中最多能套多少个套娃

核心算法和原理

• 对宽度升序排，保证在宽度不相同时，在宽度上后面的都可以套前面的，然后高度上的LIS即为最长套娃序列

• 但是宽度相同的情况下互相不能套，这种情况下求得的LIS不合题意，所以对于宽度相同的可以再对高度降序排，保证相同宽度的元素中高度更小的一定在后面，不会被加入到宽度相同的元素所在的LIS中

• tips: 传参、循环遍历时，如果参数所占用的空间较大，则传引用(auto& i : envlopes)而不要传值，否则时间巨慢

代码

class Solution {
public:
    Solution() {
        ios_base::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);
    }

    int maxEnvelopes(vector<vector<int>>& envelopes) {
        sort(envelopes.begin(), envelopes.end(), [](vector<int> &a, vector<int> &b) {
            return  (a[0] == b[0] && a[1] > b[1]) || a[0] < b[0];
        });
        
        // LIS Process
        vector<int> seq;
        for (auto &env : envelopes) {
            auto it = lower_bound(seq.begin(), seq.end(), env[1]);
            if (it == seq.end()) {
                seq.push_back(env[1]);
            } else {
                *it = env[1];
            }
        }
        return seq.size();
    }
};