每日一题 354. 俄罗斯套娃信封问题
354. 俄罗斯套娃信封问题
需要对信封排序 ,重点是再宽度相同时，逐步减少其高度
class Solution {
public:
int maxEnvelopes(vector<vector<int>>& envelopes) {
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> ans;
for(int i=0;i<envelopes.size();++i)
{
int height = envelopes[i][1];
auto it = lower_bound(ans.begin(),ans.end(),height);
if(it == ans.end())
{
ans.push_back(height);
}else{
*it = height;
}
}
return ans.size();
}
};