每日一题354
文章目录
354. 俄罗斯套娃信封问题
给定一些标记了宽度和高度的信封,宽度和高度以整数对形式 (w, h) 出现。当另一个信封的宽度和高度都比这个信封大的时候,这个信封就可以放进另一个信封里,如同俄罗斯套娃一样。
请计算最多能有多少个信封能组成一组“俄罗斯套娃”信封(即可以把一个信封放到另一个信封里面)。
说明:
不允许旋转信封。
思路
- 先对数组按递增排序
- dp数组的每个元素表示到当前位置的俄罗斯套娃的个数
- i从1到n-1, j从0到i-1依次比较
- 时间复杂度o(n2),空间复杂度o(n)
class Solution {
public:
static bool minval(vector<int> &r1, vector<int> &r2) {
return r1[0] < r2[0] || r1[0] == r2[0] && r1[1] < r2[1]; //按照递增排序,0相等的时候比较1
}
int maxEnvelopes(vector<vector<int>>& envelopes) {
int n = envelopes.size();
if (n < 2) {
return n;
}
sort(envelopes.begin(), envelopes.end(), minval);
vector<int> dp(n, 1);
for (int i = 1; i < n; ++i) {
for (int j = 0; j < i; ++j) {
if (envelopes[j][0] < envelopes[i][0] && envelopes[j][1] < envelopes[i][1]) {
dp[i] = max(dp[i], dp[j] + 1);//dp[i]表示以i结尾的满足俄罗斯套娃的个数
}
}
}
return *max_element(dp.begin(), dp.end());
}
};思路2
- 二分法,减少比较次数
- 时间复杂度o(nlgn)
- 空间复杂度o(n)
class Solution {
public:
static bool minval(vector<int> &r1, vector<int> &r2) {
return r1[0] < r2[0] || (r1[0] == r2[0] && r1[1] > r2[1]);
}
int maxEnvelopes(vector<vector<int>>& envelopes) {
int n = envelopes.size();
if (n < 2) {
return n;
}
sort(envelopes.begin(), envelopes.end(), minval);
vector<int> f = {envelopes[0][1]};
for (int i = 1; i < n; ++i) {
int num = envelopes[i][1];
if (num > f.back()) {
f.push_back(num);
} else {
auto it = lower_bound(f.begin(), f.end(), num);//如果没有找到,指向初始位置
*it = num;
}
}
return f.size();
}
};
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论