信封嵌套问题

[编程题]信封嵌套问题

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

算法知识视频讲解

小谷围做题家

package main

import "sort"

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param letters int二维数组 
 * @return int
*/
func maxLetters( letters [][]int ) int {
    n:=len(letters)
    sort.Slice(letters,func(i,j int)bool{
        return letters[i][0]<letters[j][0]
    })
    ans:=1
    dp:=make([]int,n)
    for i,lt:=range letters{
        dp[i]=1
        for j:=0;j<i;j++{
            if lt[0]>letters[j][0]&&lt[1]>letters[j][1]{
                dp[i]=max(dp[i],dp[j]+1)
            }
        }
        if ans<dp[i]{
            ans=dp[i]
        }
    }
    return ans
}

func max(a,b int)int{
    if a>b{
        return a
    }
    return b
}

发表于 2023-03-11 18:50:01 回复(0)