)
链接354. 俄罗斯套娃信封问题题解力扣LeetCode官网 - 全球极客挚爱的技术成长平台力扣LeetCode官网 - 全球极客挚爱的技术成长平台力扣LeetCode官网 - 全球极客挚爱的技术成长平台1.sort a[0] b[0] return true a[0] b[0] a[1] b[1] return true;2.dp存储的是以当前长度的最小的h是多少存储的是envelopes[i][1]因为envelopes[i][0]已经是单调递增的了class Solution { public: int maxEnvelopes(vectorvectorint envelopes) { // 宽度升序宽度相同时高度降序 sort(envelopes.begin(), envelopes.end(), [](const vectorint a, const vectorint b) { if (a[0] ! b[0]) return a[0] b[0]; return a[1] b[1]; }); // 对高度求严格递增子序列 vectorint lis; for (const auto envelope : envelopes) { int h envelope[1]; // lower_bound 保证严格递增 auto it lower_bound(lis.begin(), lis.end(), h); if (it lis.end()) { lis.push_back(h); } else { *it h; } } return lis.size(); } };class Solution { public: int maxEnvelopes(vectorvectorint envelopes) { int len envelopes.size(); if (len 0) { return 0; } sort(envelopes.begin(), envelopes.end(), [](vectorint a, vectorint b) { if (a[0] b[0]) { return true; } else if (a[0] b[0] a[1] b[1]) { return true; } return false; }); vectorint dp(len1); int top 0; dp[0] INT_MIN; for (int i 0; i len; i) { auto ite lower_bound(dp.begin(), dp.begin()top1, envelopes[i][1]); if (ite dp.begin()top1) { dp[top] envelopes[i][1]; } else { *ite envelopes[i][1]; } } return top; } };class Solution { public: int maxEnvelopes(vectorvectorint envelopes) { // 按照升序排序 auto cmp [](vectorint v1, vectorint v2) { return v1[0] v2[0] || (v1[0] v2[0] v2[1] v2[1]); }; sort(envelopes.begin(), envelopes.end(), cmp); // dp[i]表示以下标i为结尾的数字最长底层序列 vectorint dp(envelopes.size(), 1); int res 1; int n envelopes.size(); for(int i 0; i n; i) { for(int j 0; j i; j) { if(envelopes[j][1] envelopes[i][1]) { // 以i为结尾的数字可以同以j为结尾的数字增加1位 dp[i] max(dp[i], dp[j]1); } } res max(res, dp[i]); } return res; } };力扣LeetCode官网 - 全球极客挚爱的技术成长平台同宽高度必须降序否则 LIS 会误选同宽度的多个信封一、用你自己的用例演示textenvelopes [[1,3],[3,5],[6,7],[6,8],[8,4],[9,5]][6,7]和[6,8]宽度相同不能互相套。正确答案是3比如[1,3]→[3,5]→[6,7]。如果同宽高度升序排序后text[1,3], [3,5], [6,7], [6,8], [8,4], [9,5]高度序列3, 5, 7, 8, 4, 5LIS严格递增可以选出3, 5, 7, 8长度4❌问题就出在7, 8这两个高度它们来自[6,7]和[6,8]宽度都是 6实际不能同时选但升序排列让它们在高度序列里连续递增LIS 把它们都选中了。同宽高度降序排序后text[1,3], [3,5], [6,8], [6,7], [8,4], [9,5]高度序列3, 5, 8, 7, 4, 5LIS 只能选出3, 5, 8或3, 5, 7或3, 4, 5长度3✅8和7虽然相邻但8 7严格递增的 LIS不能同时选中它们。同宽度的两个信封在高度序列里最多被选一个。二、原理LIS 要求严格递增。同宽度的信封如果高度降序排列它们在高度序列里是递减的text宽度相同的几个信封高度8, 7, 4, ... 高度序列里8 → 7 → 4严格递减严格递增的 LIS 不可能同时包含递减序列里的两个元素。所以同宽度最多选一个正好符合题目“宽度必须严格递增”的要求。如果高度升序text高度序列里4 → 7 → 8严格递增LIS 会认为它们可以接在一起把同宽度的多个信封都选中结果偏大。三、更简单的例子textenvelopes [[1,1],[1,3],[2,4]]同宽升序[1,1],[1,3],[2,4]高度1,3,4LIS 3 ❌[1,1]和[1,3]同宽不能都选同宽降序[1,3],[1,1],[2,4]高度3,1,4LIS 2 ✅3,4或1,4四、一句话总结同宽高度降序是为了让同宽度的信封在高度序列里形成递减从而严格递增的 LIS 无法同时选中它们保证“同宽度最多选一个”。如果升序同宽度的信封高度递增LIS 会把它们误认为可以套娃结果偏大。你用例里的[6,7]和[6,8]就是典型升序会得到 4降序才是正确的 3。 
长河君 · 2026/10/29 10:14:41 · 阅读 1.2k 354. 俄罗斯套娃信封问题(坐标dp二分)
链接354. 俄罗斯套娃信封问题题解力扣LeetCode官网 - 全球极客挚爱的技术成长平台力扣LeetCode官网 - 全球极客挚爱的技术成长平台力扣LeetCode官网 - 全球极客挚爱的技术成长平台1.sort a[0] b[0] return true a[0] b[0] a[1] b[1] return true;2.dp存储的是以当前长度的最小的h是多少存储的是envelopes[i][1]因为envelopes[i][0]已经是单调递增的了class Solution { public: int maxEnvelopes(vectorvectorint envelopes) { // 宽度升序宽度相同时高度降序 sort(envelopes.begin(), envelopes.end(), [](const vectorint a, const vectorint b) { if (a[0] ! b[0]) return a[0] b[0]; return a[1] b[1]; }); // 对高度求严格递增子序列 vectorint lis; for (const auto envelope : envelopes) { int h envelope[1]; // lower_bound 保证严格递增 auto it lower_bound(lis.begin(), lis.end(), h); if (it lis.end()) { lis.push_back(h); } else { *it h; } } return lis.size(); } };class Solution { public: int maxEnvelopes(vectorvectorint envelopes) { int len envelopes.size(); if (len 0) { return 0; } sort(envelopes.begin(), envelopes.end(), [](vectorint a, vectorint b) { if (a[0] b[0]) { return true; } else if (a[0] b[0] a[1] b[1]) { return true; } return false; }); vectorint dp(len1); int top 0; dp[0] INT_MIN; for (int i 0; i len; i) { auto ite lower_bound(dp.begin(), dp.begin()top1, envelopes[i][1]); if (ite dp.begin()top1) { dp[top] envelopes[i][1]; } else { *ite envelopes[i][1]; } } return top; } };class Solution { public: int maxEnvelopes(vectorvectorint envelopes) { // 按照升序排序 auto cmp [](vectorint v1, vectorint v2) { return v1[0] v2[0] || (v1[0] v2[0] v2[1] v2[1]); }; sort(envelopes.begin(), envelopes.end(), cmp); // dp[i]表示以下标i为结尾的数字最长底层序列 vectorint dp(envelopes.size(), 1); int res 1; int n envelopes.size(); for(int i 0; i n; i) { for(int j 0; j i; j) { if(envelopes[j][1] envelopes[i][1]) { // 以i为结尾的数字可以同以j为结尾的数字增加1位 dp[i] max(dp[i], dp[j]1); } } res max(res, dp[i]); } return res; } };力扣LeetCode官网 - 全球极客挚爱的技术成长平台同宽高度必须降序否则 LIS 会误选同宽度的多个信封一、用你自己的用例演示textenvelopes [[1,3],[3,5],[6,7],[6,8],[8,4],[9,5]][6,7]和[6,8]宽度相同不能互相套。正确答案是3比如[1,3]→[3,5]→[6,7]。如果同宽高度升序排序后text[1,3], [3,5], [6,7], [6,8], [8,4], [9,5]高度序列3, 5, 7, 8, 4, 5LIS严格递增可以选出3, 5, 7, 8长度4❌问题就出在7, 8这两个高度它们来自[6,7]和[6,8]宽度都是 6实际不能同时选但升序排列让它们在高度序列里连续递增LIS 把它们都选中了。同宽高度降序排序后text[1,3], [3,5], [6,8], [6,7], [8,4], [9,5]高度序列3, 5, 8, 7, 4, 5LIS 只能选出3, 5, 8或3, 5, 7或3, 4, 5长度3✅8和7虽然相邻但8 7严格递增的 LIS不能同时选中它们。同宽度的两个信封在高度序列里最多被选一个。二、原理LIS 要求严格递增。同宽度的信封如果高度降序排列它们在高度序列里是递减的text宽度相同的几个信封高度8, 7, 4, ... 高度序列里8 → 7 → 4严格递减严格递增的 LIS 不可能同时包含递减序列里的两个元素。所以同宽度最多选一个正好符合题目“宽度必须严格递增”的要求。如果高度升序text高度序列里4 → 7 → 8严格递增LIS 会认为它们可以接在一起把同宽度的多个信封都选中结果偏大。三、更简单的例子textenvelopes [[1,1],[1,3],[2,4]]同宽升序[1,1],[1,3],[2,4]高度1,3,4LIS 3 ❌[1,1]和[1,3]同宽不能都选同宽降序[1,3],[1,1],[2,4]高度3,1,4LIS 2 ✅3,4或1,4四、一句话总结同宽高度降序是为了让同宽度的信封在高度序列里形成递减从而严格递增的 LIS 无法同时选中它们保证“同宽度最多选一个”。如果升序同宽度的信封高度递增LIS 会把它们误认为可以套娃结果偏大。你用例里的[6,7]和[6,8]就是典型升序会得到 4降序才是正确的 3。