百度站长自动推送wordpress,友好速搭 WordPress,淘宝客的网站是怎么做的,精准推广LeetCode 354. 俄罗斯套娃信封问题 - C 源码分析 1. 题目概述 问题描述#xff1a;给定一组信封 (w, h)#xff0c;当一个信封的宽度和高度都严格大于另一个信封时#xff0c;才能把小信封放进大信封里。求最多能套娃多少层。 示例#xff1a; 输入#xff1a;envelopes …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(vectorvectorintenvelopes){// 边界条件检查if(envelopes.empty()){return0;}// 1. 排序宽度升序宽度相同时高度降序sort(envelopes.begin(),envelopes.end(),[](constvectorinta,constvectorintb){if(a[0]b[0]){returna[1]b[1];// 宽度相同高度降序}returna[0]b[0];// 宽度升序});// 2. 提取高度数组求LISintnenvelopes.size();vectorintheights(n);for(inti0;in;i){heights[i]envelopes[i][1];}// 3. 二分查找求LISreturnlengthOfLIS(heights);}private:/** * 最长递增子序列 - 二分查找优化版 * tails[i] 表示长度为 i1 的递增子序列的最小末尾元素 * 时间复杂度 O(n log n) */intlengthOfLIS(vectorintnums){vectorinttails;for(intnum:nums){// 二分查找num在tails中的插入位置autoitlower_bound(tails.begin(),tails.end(),num);if(ittails.end()){// num大于所有tails元素可以追加到末尾tails.push_back(num);}else{// 替换找到位置的元素*itnum;}}returntails.size();}};3. 代码逐行详解3.1 排序部分sort(envelopes.begin(),envelopes.end(),[](constvectorinta,constvectorintb){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(vectorintnums){vectorinttails;// tails[i]存储长度为i1的递增子序列的最小末尾for(intnum:nums){// lower_bound 返回第一个 num 的位置autoitlower_bound(tails.begin(),tails.end(),num);if(ittails.end()){tails.push_back(num);// num更大扩展序列}else{*itnum;// 替换保持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(vectorvectorintenvelopes){if(envelopes.empty())return0;// 排序sort(envelopes.begin(),envelopes.end(),[](autoa,autob){returna[0]b[0]||(a[0]b[0]a[1]b[1]);});// LIS - 手写二分vectorinttails;for(autoe:envelopes){inthe[1];intleft0,righttails.size();// 二分查找插入位置while(leftright){intmidleft(right-left)/2;if(tails[mid]h){leftmid1;}else{rightmid;}}if(lefttails.size()){tails.push_back(h);}else{tails[left]h;}}returntails.size();}};5. 动态规划解法O(n²)classSolution{public:intmaxEnvelopes(vectorvectorintenvelopes){if(envelopes.empty())return0;// 先排序宽度升序宽度相同按高度升序sort(envelopes.begin(),envelopes.end());intnenvelopes.size();vectorintdp(n,1);intmaxLen1;for(inti1;in;i){for(intj0;ji;j){if(envelopes[i][0]envelopes[j][0]envelopes[i][1]envelopes[j][1]){dp[i]max(dp[i],dp[j]1);}}maxLenmax(maxLen,dp[i]);}returnmaxLen;}};缺点时间复杂度 O(n²)当 n10^5 时会超时。6. 性能对比分析解法时间复杂度空间复杂度适用场景排序 二分LISO(n log n)O(n)大数据量最优排序 DPO(n²)O(n)小数据量n≤5000暴力DFSO(2ⁿ)O(n)完全不实用7. 边界条件测试voidtestCases(){Solution s;// 测试1空数组vectorvectorintcase1{};assert(s.maxEnvelopes(case1)0);// 测试2单个信封vectorvectorintcase2{{1,1}};assert(s.maxEnvelopes(case2)1);// 测试3宽度相同的情况vectorvectorintcase3{{1,2},{1,3},{1,4}};assert(s.maxEnvelopes(case3)1);// 不能套娃// 测试4高度相同的情况vectorvectorintcase4{{1,2},{2,2},{3,2}};assert(s.maxEnvelopes(case4)1);// 不能套娃// 测试5正常情况vectorvectorintcase5{{5,4},{6,4},{6,7},{2,3}};assert(s.maxEnvelopes(case5)3);// 测试6完全递增vectorvectorintcase6{{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]LIS1正确。Q2: 能不能先按高度排序再按宽度处理答可以对称处理即可sort(envelopes.begin(),envelopes.end(),[](autoa,autob){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使用sortlower_bound完美配合边界处理严格递增条件确保正确性这个解法是面试中的标准答案理解排序策略的巧妙之处和 LIS 二分优化的实现是关键。