信封嵌套问题

[编程题]信封嵌套问题

热度指数：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)。

算法知识视频讲解

JavaScript

别卷啦！

不符合时间复杂度要求就当一种参考啦留着自己复习用

function maxLetters( letters ) {
    // write code here
    let  len = letters.length
    if(!len) return 0
    letters.sort((a,b)=> a[0]=== b[0]? a[1]-b[1]:a[0]-b[0])
    const dp = new Array(len).fill(1)
    dp[0] = 1
    for(let i = 1;i<len;i++){
        for(let j = 0;j<i;j++){
            if(letters[i][1]>letters[j][1] && letters[i][0] !== letters[j][0]){
                dp[i] = Math.max(dp[i], dp[j]+1)
            }
    }
}
    return Math.max(...dp)
}

发表于 2021-01-28 21:02:49 回复(0)