本文涉及的基础知识点
题目
给你一个二维整数数组 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 <= 105
envelopes[i].length == 2
1 <= wi, hi <= 105
超时解法
有两个地方可能超时：
一，std::map<int, int> dp = mPreYToNum;
二，for (; (ij != dp.end()) && (ij->second > len); ++ij);
一处的时间复杂度是:O(n)，最多有n个元素，所以总时间复杂度是O(n*n)，会引起超时。
二处，总时间复杂度是O(n)，最多删除n次，每个元素最多只会被删除一次。
代码
class Solution { public: int maxEnvelopes(vector<vector>& envelopes) { std::map<int, vector> mXToYS; for (const auto& v : envelopes) { mXToYS[v[0]].emplace_back(v[1]); } std::map<int, int> mPreYToNum;//y值对应最大数量，y值越大，对应的数量越大，否则被淘汰了 int iMax = 0; for (const auto& it : mXToYS) { std::map<int, int> dp = mPreYToNum; for (const auto& y : it.second) { int len = 0; {//计算长度 const auto it = mPreYToNum.lower_bound(y); len = 1 + ((mPreYToNum.begin() == it) ? 0 : std::prev(it)->second); iMax = max(iMax, len); } { const auto it = dp.lower_bound(y); auto ij = it; for (; (ij != dp.end()) && (ij->second > len); ++ij); dp.erase(it, ij); if (!dp.count(y)) { dp[y] = len; } } } mPreYToNum.swap(dp); }
return iMax; }
};
测试用例
template void Assert(const T& t1, const T& t2) { assert(t1 == t2); } template void Assert(const vector& v1, const vector& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { Assert(v1[i] ,v2[i]); } } int main() { Solution slu; vector<vector> envelopes; int res = 0; envelopes = { {5,4},{6,4},{6,7},{2,3} }; res = slu.maxEnvelopes(envelopes); Assert(res, 3); envelopes = { {1,1},{1,1},{1,1} }; res = slu.maxEnvelopes(envelopes); Assert(res, 1); envelopes = { {1,1},{2,2},{2,3} }; res = slu.maxEnvelopes(envelopes); Assert(res, 2); envelopes = { {1,2},{2,3},{3,4},{3,5},{4,5},{5,5},{5,6},{6,7},{7,8} }; res = slu.maxEnvelopes(envelopes); Assert(res, 7);
//CConsole::Out(res);
}
正确解法
变量含义
| mXToYS | key为envelopes的x，值为envelopes的y |
| mYToNum | [x取[0,x)， y对应最大套娃数量 |
| vector<pair<int, int>> vYNum | 当前x，各y对应数量 |
注意：
x相同，无法套娃，所以必须等当前x处理完毕，才能更新mYToNum。
y值越大，对应的数量越大，否则被淘汰了。所以mYToNum的键和值都是升序。
y小于当前y的，不会淘汰当前y，因为当前长度就是小于y的最大长度+1。
所以只会被相等的y淘汰。
当前y 可能淘汰比当前y大的。
代码
class Solution { public: int maxEnvelopes(vector<vector>& envelopes) { std::map<int, vector> mXToYS; for (const auto& v : envelopes) { mXToYS[v[0]].emplace_back(v[1]); } std::map<int, int> mYToNum;//y值对应最大数量 int iMax = 0; for (const auto& it : mXToYS) { vector<pair<int, int>> vYNum; for (const auto& y : it.second) { const auto it = mYToNum.lower_bound(y); const int num = 1 + ((mYToNum.begin() == it) ? 0 : std::prev(it)->second); iMax = max(iMax, num); vYNum.emplace_back(y, num); } for(const auto[y,num]: vYNum) { const auto it = mYToNum.lower_bound(y); auto ij = it; for (; (ij != mYToNum.end()) && (ij->second <= num); ++ij); mYToNum.erase(it, ij); if (!mYToNum.count(y)) { mYToNum[y] = num; } } } return iMax; } };
2023年1月旧代码
class Solution { public: int maxEnvelopes(vector<vector>& envelopes) { std::map<int, vector> mWidthToHeights; for (const auto& v : envelopes) { mWidthToHeights[v[0]].push_back(v[1]); } int iMax = 1; std::map<int, int> mHeightNum; for ( auto& it : mWidthToHeights) { sort(it.second.begin(), it.second.end(),std::greater()); for (auto& height : it.second) { auto it = mHeightNum.lower_bound(height); int iNum =1; if (mHeightNum.begin() != it) {//没有套 auto ij = it; –ij; iNum = ij->second + 1; } iNum = max(iNum,mHeightNum[height]); auto ij = it; while ( (ij != mHeightNum.end())&& ( ij->second < iNum)) { ij++; } mHeightNum.erase(it, ij); mHeightNum[height] = max(mHeightNum[height], iNum); iMax = max(iMax, mHeightNum[height]); } } return iMax; } };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法，请下载《闻缺陷则喜算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
| 充满正能量得对大家说 |
| 闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。 |
| 墨家名称的来源：有所得以墨记之。 |
| 算法终将统治宇宙，而我们统治算法。《喜缺全书》 |
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开
发环境： VS2022 C++17
