0%

LeetCode: 354. Russian Doll Envelopes

先排序,然后按照最长子序列的方法找结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
int maxEnvelopes(vector<pair<int, int>>& envelopes) {
if(envelopes.size()<2)
return envelopes.size();
sort(envelopes.begin(), envelopes.end(), [](pair<int,int> &lhs,pair<int,int> &rhs){
if(lhs.first!=rhs.first)
return lhs.first<rhs.first;
else return lhs.second<rhs.second;
});
vector<int> dp(envelopes.size(), 1);
int ret=1;
for(int i=0;i<envelopes.size();++i)
{
for(int j=i-1;j>=0;--j)
{
if(envelopes[j].first<envelopes[i].first &&
envelopes[j].second<envelopes[i].second)
{
dp[i]=max(dp[j]+1,dp[i]);
}
ret=max(dp[i],ret);
}
}
return ret;
}
};