)
LeetCode 354. 俄罗斯套娃信封问题 - C++ 源码分析
1. 题目概述
问题描述：给定一组信封(w, h)，当一个信封的宽度和高度都严格大于另一个信封时，才能把小信封放进大信封里。求最多能套娃多少层。
示例：
输入：envelopes=[[5,4],[6,4],[6,7],[2,3]]输出：3解释：[2,3]->[5,4]->[6,7]2. C++ 最优解法（排序 + 二分查找）
classSolution{public:intmaxEnvelopes(vector<vector<int>>&envelopes){// 边界条件检查if(envelopes.empty()){return0;}// 1. 排序：宽度升序，宽度相同时高度降序sort(envelopes.begin(),envelopes.end(),[](constvector<int>&a,constvector<int>&b){if(a[0]==b[0]){returna[1]>b[1];// 宽度相同，高度降序}returna[0]<b[0];// 宽度升序});// 2. 提取高度数组，求LISintn=envelopes.size();vector<int>heights(n);for(inti=0;i<n;i++){heights[i]=envelopes[i][1];}// 3. 二分查找求LISreturnlengthOfLIS(heights);}private:/** * 最长递增子序列 - 二分查找优化版 * tails[i] 表示长度为 i+1 的递增子序列的最小末尾元素 * 时间复杂度 O(n log n) */intlengthOfLIS(vector<int>&nums){vector<int>tails;for(intnum:nums){// 二分查找num在tails中的插入位置autoit=lower_bound(tails.begin(),tails.end(),num);if(it==tails.end()){// num大于所有tails元素，可以追加到末尾tails.push_back(num);}else{// 替换找到位置的元素*it=num;}}returntails.size();}};3. 代码逐行详解
3.1 排序部分
sort(envelopes.begin(),envelopes.end(),[](constvector<int>&a,constvector<int>&b){if(a[0]==b[0]){returna[1]>b[1];// 关键：宽度相同时高度降序}returna[0]<b[0];// 主排序：宽度升序});为什么这样排序？
| 排序规则 | 原因 |
|---|---|
| 宽度升序 | 保证后面的信封宽度 ≥ 前面的 |
| 宽度相同时高度降序 | 避免相同宽度的信封被同时选中（因为宽度相等时不能套娃） |
示例验证：
输入：[[5,4],[6,4],[6,7],[2,3]]排序过程：[2,3]→ 高度=3[5,4]→ 高度=4[6,7]→ 高度=7(宽度相同，高度大的在前)[6,4]→ 高度=4(宽度相同，高度小的在后)高度数组：[3,4,7,4]求LIS → 最大长度=3([3,4,7]或[3,4,4]?注意严格递增，所以[3,4,7])3.2 LIS 二分查找部分
intlengthOfLIS(vector<int>&nums){vector<int>tails;// tails[i]存储长度为i+1的递增子序列的最小末尾for(intnum:nums){// lower_bound 返回第一个 >= num 的位置autoit=lower_bound(tails.begin(),tails.end(),num);if(it==tails.end()){tails.push_back(num);// num更大，扩展序列}else{*it=num;// 替换，保持tails数组递增且尽可能小}}returntails.size();}tails数组变化过程：
nums=[3,4,7,4]初始 tails=[]处理3:lower_bound([],3)→end()→ tails=[3]处理4:lower_bound([3],4)→end()→ tails=[3,4]处理7:lower_bound([3,4],7)→end()→ tails=[3,4,7]处理4:lower_bound([3,4,7],4)→ 位置1→ tails=[3,4,7](替换tails[1]=4)最终 tails=[3,4,7]，长度为34. 另一种实现方式（手写二分）
classSolution{public:intmaxEnvelopes(vector<vector<int>>&envelopes){if(envelopes.empty())return0;// 排序sort(envelopes.begin(),envelopes.end(),[](auto&a,auto&b){returna[0]<b[0]||(a[0]==b[0]&&a[1]>b[1]);});// LIS - 手写二分vector<int>tails;for(auto&e:envelopes){inth=e[1];intleft=0,right=tails.size();// 二分查找插入位置while(left<right){intmid=left+(right-left)/2;if(tails[mid]<h){left=mid+1;}else{right=mid;}}if(left==tails.size()){tails.push_back(h);}else{tails[left]=h;}}returntails.size();}};5. 动态规划解法（O(n²)）
classSolution{public:intmaxEnvelopes(vector<vector<int>>&envelopes){if(envelopes.empty())return0;// 先排序（宽度升序，宽度相同按高度升序）sort(envelopes.begin(),envelopes.end());intn=envelopes.size();vector<int>dp(n,1);intmaxLen=1;for(inti=1;i<n;i++){for(intj=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);}}maxLen=max(maxLen,dp[i]);}returnmaxLen;}};缺点：时间复杂度 O(n²)，当 n=10^5 时会超时。
6. 性能对比分析
| 解法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 排序 + 二分LIS | O(n log n) | O(n) | 大数据量（最优） |
| 排序 + DP | O(n²) | O(n) | 小数据量（n≤5000） |
| 暴力DFS | O(2ⁿ) | O(n) | 完全不实用 |
7. 边界条件测试
voidtestCases(){Solution s;// 测试1：空数组vector<vector<int>>case1={};assert(s.maxEnvelopes(case1)==0);// 测试2：单个信封vector<vector<int>>case2={{1,1}};assert(s.maxEnvelopes(case2)==1);// 测试3：宽度相同的情况vector<vector<int>>case3={{1,2},{1,3},{1,4}};assert(s.maxEnvelopes(case3)==1);// 不能套娃// 测试4：高度相同的情况vector<vector<int>>case4={{1,2},{2,2},{3,2}};assert(s.maxEnvelopes(case4)==1);// 不能套娃// 测试5：正常情况vector<vector<int>>case5={{5,4},{6,4},{6,7},{2,3}};assert(s.maxEnvelopes(case5)==3);// 测试6：完全递增vector<vector<int>>case6={{1,1},{2,2},{3,3},{4,4}};assert(s.maxEnvelopes(case6)==4);cout<<"所有测试通过！"<<endl;}8. 面试常见问题
Q1: 为什么宽度相同时要按高度降序排序？
答：假设宽度相同按高度升序：[[5,4],[5,6]]，高度数组[4,6]，LIS 会得到 2，但这是错误的，因为宽度相同不能套娃。降序后[[5,6],[5,4]]，高度数组[6,4]，LIS=1，正确。
Q2: 能不能先按高度排序再按宽度处理？
答：可以，对称处理即可：
sort(envelopes.begin(),envelopes.end(),[](auto&a,auto&b){if(a[1]==b[1])returna[0]>b[0];returna[1]<b[1];});// 然后对宽度求LISQ3: 如何处理三维套娃问题？
答：三维问题（长、宽、高）需要更复杂的处理：
- 固定一维排序，对剩余两维求二维LIS
- 或者用三维偏序 + CDQ分治
9. 总结
LeetCode 354 的 C++ 解法核心要点：
- 排序策略：宽度升序 + 宽度相同高度降序
- LIS算法：二分查找优化到 O(n log n)
- STL使用：
sort+lower_bound完美配合 - 边界处理：严格递增条件确保正确性
这个解法是面试中的标准答案，理解排序策略的巧妙之处和 LIS 二分优化的实现是关键。
