1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public:
int maxEnvelopes(vector<vector<int>>& envelopes) {
if (envelopes.empty()) return 0;
sort(envelopes.begin(), envelopes.end(), [](const vector<int>& a, const vector<int>& b) {
return a[0] < b[0] || (a[0] == b[0] && a[1] > b[1]);
});
vector<int> dp{envelopes[0][1]};
for (int i = 1; i < envelopes.size(); ++i) {
int num = envelopes[i][1];
if (num > dp.back()) {
dp.emplace_back(num);
} else {
auto it = lower_bound(dp.begin(), dp.end(), num);
*it = num;
}
}
return dp.size();
}
};
|