商城类网站成都专业做网站

商城类网站,成都专业做网站,ppt模板免费下载古风,石景山网站建设多少钱LeetCode 354. 俄罗斯套娃信封问题 - 源码分析 1. 题目概述 问题描述#xff1a;给定一堆信封的宽度和高度 (w, h)#xff0c;当一个信封的宽度和高度都大于另一个信封时#xff0c;就可以把小信封放进大信封里。问最多能套娃多少层#xff08;每个信封只能用一次#xff…LeetCode 354. 俄罗斯套娃信封问题 - 源码分析1. 题目概述问题描述给定一堆信封的宽度和高度(w, h)当一个信封的宽度和高度都大于另一个信封时就可以把小信封放进大信封里。问最多能套娃多少层每个信封只能用一次。示例输入envelopes [[5,4],[6,4],[6,7],[2,3]] 输出3 解释最多信封的个数为 3, 组合为: [2,3] - [5,4] - [6,7]。2. 问题分析这是一个二维最长递增子序列问题。核心难点在于二维约束需要同时满足宽度和高度都递增相等处理宽度相等时不能套娃3. 核心解法思路关键转换按宽度升序排序宽度相同时按高度降序排序对高度数组求最长递增子序列(LIS)为什么这样排序宽度升序保证后面的信封宽度≥前面的宽度相同时高度降序避免相同宽度的信封相互套娃因为宽度相等时不能套娃所以高度降序保证这些信封在LIS中不会同时被选中4. 最优解法排序 二分查找classSolution{publicintmaxEnvelopes(int[][]envelopes){// 边界条件if(envelopesnull||envelopes.length0){return0;}// 1. 排序宽度升序宽度相同时高度降序Arrays.sort(envelopes,(a,b)-{if(a[0]b[0]){returnb[1]-a[1];// 宽度相同高度降序}returna[0]-b[0];// 宽度升序});// 2. 提取高度数组求最长递增子序列intnenvelopes.length;int[]heightsnewint[n];for(inti0;in;i){heights[i]envelopes[i][1];}returnlengthOfLIS(heights);}/** * 求最长递增子序列的长度二分查找优化版 * 时间复杂度 O(n log n) */privateintlengthOfLIS(int[]nums){int[]tailsnewint[nums.length];intsize0;for(intnum:nums){// 二分查找num在tails数组中的插入位置intleft0,rightsize;while(leftright){intmidleft(right-left)/2;if(tails[mid]num){leftmid1;}else{rightmid;}}// 更新tails数组tails[left]num;if(leftsize){size;}}returnsize;}}5. 详细算法图解5.1 排序过程示例原始数组[[5,4],[6,4],[6,7],[2,3]] 排序规则 1. 按宽度升序 2. 宽度相同时高度降序 排序后 [2,3] → 高度3 [5,4] → 高度4 [6,7] → 高度7 (宽度相同高度降序) [6,4] → 高度4 高度数组[3,4,7,4]5.2 LIS计算过程高度数组[3,4,7,4] 求最长递增子序列长度 初始 tails []size 0 处理3 二分查找插入位置left0, right0 → left0 tails[0]3, size1 tails [3] 处理4 二分查找插入位置left0, right1 → mid0, tails[0]34 → left1 left1, right1 → 插入位置1 tails[1]4, size2 tails [3,4] 处理7 二分查找插入位置left0, right2 → mid1, tails[1]47 → left2 left2, right2 → 插入位置2 tails[2]7, size3 tails [3,4,7] 处理4 二分查找插入位置left0, right3 → mid1, tails[1]44 → right1 left0, right1 → mid0, tails[0]34 → left1 left1, right1 → 插入位置1 tails[1]4, size3 (不变) tails [3,4,7] 最终 LIS 长度 36. 其他解法对比6.1 动态规划解法O(n²)privateintlengthOfLIS_DP(int[]nums){intnnums.length;int[]dpnewint[n];Arrays.fill(dp,1);intmaxLen1;for(inti1;in;i){for(intj0;ji;j){if(nums[i]nums[j]){dp[i]Math.max(dp[i],dp[j]1);}}maxLenMath.max(maxLen,dp[i]);}returnmaxLen;}时间复杂度O(n²) - 数据量大时会超时6.2 解法对比解法时间复杂度空间复杂度优点缺点排序LIS二分O(n log n)O(n)最优解面试推荐需要理解LIS二分思想排序DPO(n²)O(n)思路直观大数据量会超时DFS回溯O(2ⁿ)O(n)最直观完全不可行7. 边界情况处理publicintmaxEnvelopes(int[][]envelopes){// 1. 空数组if(envelopesnull||envelopes.length0){return0;}// 2. 单个信封if(envelopes.length1){return1;}// 3. 宽度相同的情况// 排序时已处理// 4. 高度相同的情况// LIS算法要求严格递增所以不会重复计算// 5. 大数值情况// 使用int足够题目给的范围在int内}8. 常见错误及注意事项8.1 错误宽度相同时没有降序处理// 错误写法Arrays.sort(envelopes,(a,b)-a[0]-b[0]);// 这样排序后[[5,4],[6,4],[6,7]]// 高度数组[4,4,7] → LIS2错误// 正确应为3[2,3]-[5,4]-[6,7]8.2 正确宽度相同时高度降序// 正确写法Arrays.sort(envelopes,(a,b)-{if(a[0]b[0]){returnb[1]-a[1];// 高度降序}returna[0]-b[0];// 宽度升序});9. 面试要点核心思路将二维问题转化为一维LIS问题关键技巧宽度相同时高度降序排序优化重点用二分查找优化LIS边界讨论如何处理相等情况为什么高度要降序能否用其他方法10. 总结LeetCode 354的关键点排序策略宽度升序 宽度相同时高度降序LIS优化用二分查找将时间复杂度降到O(n log n)问题转化二维LIS → 一维LIS这个解法是面试中的标准答案理解排序策略的巧妙之处和LIS二分优化的实现是关键。