354. 俄罗斯套娃信封问题 - 力扣LeetCode354. 俄罗斯套娃信封问题 - 给你一个二维整数数组 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 105https://leetcode.cn/problems/russian-doll-envelopes/题目大意给你一个二维数组envelopes其中envelopes[i] [w, h]代表一个信封的宽度和高度。 当且仅当一个信封的宽和高都严格小于另一个信封的宽高时这个信封可以套进另一个里面。 问最多能套多少层信封解法先对这个进行进行排序宽度不同按宽度从小到大排序宽度相同按高度从大到小排序。接下来就是和求最长递增序列一样的方法,贪心加二分维护一个数组tailstails[i]的含义长度为 i1 的递增子序列末尾最小的数字遍历每一个元素 x如果 x tails.back ()直接追加到 tails子序列变长如果 x ≤ tails.back ()在 tails 里二分找到第一个 ≥x 的位置替换成 x找到插入数的位置是采用二分,速度更快class Solution { public: int maxEnvelopes(vectorvectorint envelopes) { sort(envelopes.begin(), envelopes.end(), [](vectorint a, vectorint b) { return a[0] ! b[0] ? a[0] b[0] : a[1] b[1]; }); int nenvelopes.size(); vectorintret; ret.push_back(envelopes[0][1]); for(int i1;in;i) { int benvelopes[i][1]; if(bret.back()) { ret.push_back(b); } else{ int left0,rightret.size()-1; while(leftright) { int midleft(right-left)/2; if(bret[mid]) rightmid; else leftmid1; } ret[left]b; } } return ret.size(); } };