***Leetcode 354. Russian Doll Envelopes

本文主要是介绍***Leetcode 354. Russian Doll Envelopes，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

https://leetcode.com/problems/russian-doll-envelopes/description/

LIS就能过掉

然后暴力O(n^2)的写法

bool cmp_small(pair<int, int> a, pair<int, int>b) {if (a.first == b.first) return a.second > b.second;else return a.first < b.first;
}class Solution {
public:int maxEnvelopes(vector<pair<int, int>>& envelopes) {if (envelopes.size() == 1) return 1;sort(envelopes.begin(), envelopes.end(), cmp_small);vector<int> dp(envelopes.size()+1, 0);int ans = 0;for (int i = 0; i < envelopes.size(); i++) {bool ch = false;for (int j = 0; j < i; j++) {if ( envelopes[j].first < envelopes[i].first && envelopes[j].second < envelopes[i].second )dp[i] = max(dp[i], dp[j] + 1), ch = true;}if (!ch) dp[i] = 1;ans = max(ans, dp[i]);}return ans;}
};

另外LIS有O(nlog(n))的写法：

LIS的nlogn的方程 dp[i]表示，最长公共子序列 第[i]个的最小值

bool cmp_small(pair<int, int> a, pair<int, int>b) {if (a.first == b.first) return a.second > b.second;else return a.first < b.first;
}class Solution {
public:int maxEnvelopes(vector< pair<int, int> >& ens) {if(ens.size() <= 1) return ens.size();sort(ens.begin(), ens.end(), cmp_small);// int dp[ens.size()+1] = {0};vector< int > dp;for (auto v : ens) {int pos = lower_bound( dp.begin(), dp.end(), v.second ) - dp.begin() ;if (pos >= dp.size()) {dp.push_back(v.second);} else {dp[pos]  = v.second;}}return dp.size();}
};

这篇关于***Leetcode 354. Russian Doll Envelopes的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---