首页 > 代码库 > 第十二周 Leetcode 354. Russian Doll Envelopes(HARD) LIS问题
第十二周 Leetcode 354. Russian Doll Envelopes(HARD) LIS问题
Leetcode354 暴力的方法是显而易见的 O（n^2）构造一个DAG找最长链即可。
也有办法优化到O（nlogn）
注意 信封的方向是不能转换的。
对第一维从小到大排序，第一维相同第二维从大到小排序。
维护一个符合题意的队列，当队列中的第二维均比当前信封的第二维小时，必然可以增加到队尾。
如果不然，可以让当前信封作为“替补”，它可以在恰当的时候代替恰好比它大的信封。
当替补们足够替换所有已有信封时，就可以增加新的信封了。
比较抽象，不过这个技巧很有趣。
看代码吧，很清晰。
class Solution {
public:
static bool cmp_first(const pair<int, int>& i, const pair<int, int>& j) {
if (i.first == j.first)
return i.second > j.second;
return i.first < j.first;
}
int maxEnvelopes(vector<pair<int, int>>& envelopes) {
sort(envelopes.begin(), envelopes.end(), cmp_first);
vector<int> dp;
for (int i = 0; i < envelopes.size(); ++i) {
auto itr = lower_bound(dp.begin(), dp.end(), envelopes[i].second);
if (itr == dp.end()) {
dp.push_back(envelopes[i].second);
} else {
*itr = envelopes[i].second;
}
}
return dp.size();
}
};
第十二周 Leetcode 354. Russian Doll Envelopes(HARD) LIS问题
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。