目录
力扣354. 俄罗斯套娃信封问题
解析代码1_动态规划（超时）
解析代码2_重写排序+贪心+二分
力扣354. 俄罗斯套娃信封问题
354. 俄罗斯套娃信封问题
难度 困难
给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。
当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
注意：不允许旋转信封。
示例 1：
输入：envelopes = [[5,4],[6,4],[6,7],[2,3]] 输出：3 解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。
示例 2：
输入：envelopes = [[1,1],[1,1],[1,1]] 输出：1
提示：
1 <= envelopes.length <= 10^5envelopes[i].length == 21 <= wi, hi <= 10^5
class Solution {
public:
int maxEnvelopes(vector<vector<int>>& envelopes) {
}
};解析代码1_动态规划（超时）
将数组按照左端点排序之后，问题就转化成了最长递增子序列模型，那接下来我们就可以用解决最长递增子序列的经验，来解决这个问题（会超时，但还是建议敲一下代码）。
- 状态表示：dp[i] 表示：以 i 位置的信封为结尾的所有套娃序列中，最长的套娃序列的长度。
- 状态转移方程：dp[i] = max(dp[j] + 1) 其中 0 <= j < i && e[i][0] > e[j][0] && e[i][1] > e[j][1] 。
- 初始化：全部初始化为 1 。
- 填表顺序：从左往右。
- 返回值：整个 dp 表中的最大值。
class Solution {
public:
int maxEnvelopes(vector<vector<int>>& envelopes) {
sort(envelopes.begin(), envelopes.end());
int n = envelopes.size(), ret = 1;
vector<int> dp(n, 1);
for(int i = 1; i < n; ++i)
{
for(int j = 0; j < i; ++j)
{
if(envelopes[i][0] > envelopes[j][0] && envelopes[i][1] > envelopes[j][1])
{
dp[i] = max(dp[i], dp[j] + 1);
}
}
ret = max(ret, dp[i]);
}
return ret;
}
};
解析代码2_重写排序+贪心+二分
当我们把整个信封按照下面的规则排序之后：
- 左端点不同的时候：按照左端点从小到大排序。
- 左端点相同的时候：按照右端点从大到小排序
此时问题就变成了仅考虑信封的右端点，完完全全的变成的最长递增子序列的模型。那么我们就可以用贪心 + 二分优化我们的算法。
class Solution {
public:
int maxEnvelopes(vector<vector<int>>& envelopes) {
sort(envelopes.begin(), envelopes.end(), [&](vector<int>& e1, vector<int>& e2)
{
return e1[0] != e2[0] ? e1[0] < e2[0] : e1[1] > e2[1];
});
vector<int> ret;
ret.push_back(envelopes[0][1]);
for(auto& e : envelopes)
{
if(e[1] > ret.back())
{
ret.push_back(e[1]);
}
else // 二分找到要放的位置（找大于等于e[1]的左端点）
{
int left = 0, right = ret.size() - 1;
while(left < right)
{
int mid = (left + right) >> 1;
if(ret[mid] < e[1])
left = mid + 1;
else
right = mid;
}
ret[left] = e[1];
}
}
return ret.size();
}
};
