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

发表于 更新于 分类于 Valine：
本文字数： 83 阅读时长 ≈ 1 分钟

354. 俄罗斯套娃信封问题

思路

  1. 使用lambda表达式重载运算符
  2. dp

拓展

  1. 300. 最长递增子序列
  2. const auto&只读取不修改
    auto&读取，可修改

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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) {
            if(e1[0]==e2[0]) return e1[1]>e2[1];
            return e1[0] < e2[0];
        });

        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());
    }
};