返回题库|

信封嵌套问题

困难美团

信封嵌套问题

困难美团动态规划

题目描述

给你一个二维整数数组 envelopes,其中 envelopes[i] = [wi, hi] 表示第 i 个信封的宽度和高度。当另一个信封的宽度和高度都比这个信封大的时候,这个信封就可以放进另一个信封里。请计算最多能有多少个信封能组成一组俄罗斯套娃信封。将问题转化为最长递增子序列问题:按宽度升序排序,宽度相同时按高度降序排序,然后对高度序列求 LIS。

示例

输入:envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出:3
solution.ts
输出结果
点击「运行代码」按钮查看结果...