信封嵌套问题

[编程题]信封嵌套问题

热度指数：4319 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给 n 个信封的长度和宽度。如果信封 a 的长和宽都小于信封 b ，那么信封 a 可以放到信封 b 里，请求出信封最多可以嵌套多少层。

数据范围： $1 \le n \le 2\times10^3$ ， $1 \le letters[i][0], letters[i][1] \le 2\times10^3$

要求：空间复杂度 $O(n)\$ ，时间复杂度 $O(n^2) \$
进阶：空间复杂度 $O(n)$ ，时间复杂度 $O(nlogn)$

示例1

输入

[[3,4],[2,3],[4,5],[1,3],[2,2],[3,6],[1,2],[3,2],[2,4]]

输出

说明

从里到外分别是{1，2}，{2，3}，{3，4}，{4，5}。

示例2

输入

[[1,4],[4,1]]

输出

备注:

时间复杂度O(nlog n)，空间复杂度O(n)。

算法知识视频讲解

馒头2020

发表于 2021-03-25 15:57:29

题目描述描述转载自力扣《354. 俄罗斯套娃信封问题》给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。请计算最多能展开全文

xqxls

发表于 2021-07-29 19:45:08

题意整理给定n个信封。将长和宽较大的信封套在长和宽较小的信封上（必须严格大于）。方法一（动态规划） 1.解题思路当信封长度从小到大排列的时候，我们只需要让对应的宽度也从小到大就能完成信封嵌套，而让宽度从小到大排列，可以转化为求宽度序列的最长递增子序列。但是如果信封长度相同，宽度如何处理呢展开全文

泪无声呢

发表于 2021-08-03 17:55:27

信封嵌套问题问题描述：给n个信封的长度和宽度。如果信封A的长和宽都小于信封B，那么信封A可以放到信封B里，请求出信封最多可以嵌套多少层。示例1 输入：[[3,4],[2,3],[4,5],[1,3],[2,2],[3,6],[1,2],[3,2],[2,4]] 返回值：展开全文

神游星宇

发表于 2021-10-22 23:25:35

import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param letters int二维数组 * 展开全文

牛客500979850号

发表于 2021-08-04 10:25:37

题意：给 n 个信封的长度和宽度。如果信封 A 的长和宽都小于信封 B ，那么信封 A 可以放到信封 B 里，请求出信封最多可以嵌套多少层。方法一:动态规划如下方法二中的解题思路,不同之处是在于寻找dp中不小于letters[i][1]的最小值直接简单遍历寻找. class Soluti 展开全文

猫头鹰的咖啡馆

发表于 2021-10-27 18:13:41

class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param letters intvector<vector<>> 展开全文

猫头鹰的咖啡馆

发表于 2021-10-20 11:51:50

class Solution { /* 1，将二维问题降道一维，最长递增子序列。计算能有多少个信封组成俄罗斯套娃=计算宽度数组中最长递增子序列。 2，按照宽度递增排序，高度数组中最大递增子序列的长度就是能有多少个信封组成俄罗斯套娃。 3，宽度不同时，按照增序排列，宽度相同时，按照递减排列，防止[6 展开全文