LeetCode354(2021.3.4)

LC354. 俄罗斯套娃信封问题

class Solution {
public:
    int maxEnvelopes(vector<vector<int>>& envelopes) {
        if (envelopes.empty()) return 0;
        int n = envelopes.size();
        sort(envelopes.begin(), envelopes.end(), [](const auto& e1, const auto& e2) {
            return e1[0] < e2[0] || (e1[0] == e2[0] && e1[1] > e2[1]);
        });
        vector<int> f(n, 1);
        for (int i = 1; i < n; ++i)
            for (int j = 0; j < i; ++j)
                if (envelopes[j][1] < envelopes[i][1]) f[i] = max(f[i], f[j] + 1);
        return *max_element(f.begin(), f.end());
    }
};

发表评论