[LeetCode]Russian Doll Envelopes

这道题和Longest Increasing Subsequence是一样的，这道题找最多的Russian Doll就是找sort之后后最长的递增序列，递增的标准是两个dimension都要大于之前的元素。同样我们也有两种方法。
第一种方法，我们用envelopes[i]表示输入数组的第i个元素，dp[i]来表示以第i个元素结尾的最长递增子序列的长度，那么我们有递推公式：

• dp[i] = max(dp[j]) + 1, where envelopes[i].first > envelopes[j].first && envelopes[i].second > envelopes[j].second

时间复杂度 O(n ^ 2)，空间复杂度O(n)，代码如下：

	class Solution {
	public:
	int maxEnvelopes(vector<pair<int, int>>& envelopes) {
	int len = envelopes.size(), res = 1;
	if(!len)return 0;
	auto comp = [](const pair<int, int>& p1, const pair<int, int>& p2){return p1.first == p2.first? p1.second < p2.second: p1.first < p2.first;};
	sort(envelopes.begin(), envelopes.end(), comp);
	vector<int> dp(len, 1);
	for(int i = 1; i < len; ++i)
	{
	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);
	}
	res = max(dp[i], res);
	}
	return res;
	}
	};

view raw Russian Doll Envelopes_1.cpp hosted with ❤ by GitHub

第二种方法，我们对envelopes按照x轴的从小到大sort，如果x轴大小相同，按照y轴大小递减地排序，这样做的目的是为了防止x轴大小相同的元素被考虑进相同的increasing  subsequence，比如[4, 500], [4, 600]，显然其不构成递增序列，所以我们先考虑[4,600]再考虑[4,500]的话，我们就不用担心这种问题了。用dp[i]表示长度为i的按y轴大小递增的子序列的结尾的最小值，同样对于每一个我们遇到的数envelopes[i]:

• 如果envelopes[i].second > dp.back()，dp.push_back(envelopes[i].second)
• 如果envelopes[i].second <= dp.back(), 代表我们可以让某个长度为k的递增序列的结尾的值更小。我们binary search找到envelopes[i].second对应的insert postion，如果dp中不存在envelopes[i].second，我们找大于envelopes[i].second的最小值dp[k]，这代表envelopes[i]可以和之前的dp[k - 1]组成结尾更小的长度为k的递增子序列；如果dp中已经存在envelopes[i].second，我们啥也不做。

值得注意的是我们binary search找insert position的时候，对于长度为len的数，我们可以从[0, len]开始搜而不是[0, len - 1]，跳出条件是lo >= hi，这样对于insert postion在array末尾的数我们可以handle地更加简洁。

时间复杂度O(n * log n)，空间复杂度O(k)，k为Longest Increasing Subsequence的长度，代码如下：

	class Solution {
	public:
	int maxEnvelopes(vector<pair<int, int>>& envelopes) {
	int len = envelopes.size();
	if(!len)return 0;
	auto comp = [](const pair<int, int>& p1, const pair<int, int>& p2){return p1.first == p2.first? p1.second > p2.second: p1.first < p2.first;};
	sort(envelopes.begin(), envelopes.end(), comp);
	vector<int> dp;
	for(auto& envelope : envelopes)
	{
	if(dp.empty() || dp.back() < envelope.second)
	{
	dp.push_back(envelope.second);
	continue;
	}
	int pos = search(dp, envelope.second);
	if(pos < dp.size())dp[pos] = envelope.second;
	}
	return dp.size();
	}
	private:
	int search(vector<int>& dp, int height)
	{
	int lo = 0, hi = dp.size();
	while(lo < hi)
	{
	int mid = lo + (hi - lo) / 2;
	if(dp[mid] < height)lo = mid + 1;
	else if(dp[mid] > height)hi = mid;
	else return mid;
	}
	return lo;
	}
	};

view raw Russian Doll Envelopes.cpp hosted with ❤ by GitHub