首页 > 试题广场 > 信封嵌套问题
[编程题]信封嵌套问题
  • 热度指数:179 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给n个信封的长度和宽度。如果信封A的长和宽都小于信封B,那么信封A可以放到信封B里,请求出信封最多可以嵌套多少层。
示例1

输入

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

输出

4

说明

从里到外分别是{1,2},{2,3},{3,4},{4,5}。 
示例2

输入

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

输出

1

备注:
时间复杂度O(nlog n),空间复杂度O(n)。

动态规划+二分查找
时间复杂度O(nlogn)
空间复杂度O(n)
1.将数组按照从小到大排序;
2.维护两个数组f,g;f[i]表示第i个信封能够嵌套的层数,g[i]表示嵌套层数为i的信封中最后一个信封宽度的最小值;g是单调递增的序列;
3.从前往后遍历数组,保证g数组中信封的长度小于当前信封;利用二分从g数组中查找宽度小于当前数组的最后一个嵌套信封,记其层数为x,当前信封能够嵌套的最大层数就是x+1。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param letters intvector<vector<>> 
     * @return int
     */
    int maxLetters(vector<vector<int> >& w) {
        // write code here
        sort(w.begin(), w.end());
        int n = w.size();
        vector<int> f(n, 0), g(1, 0);
        int ans = 0;
        for (int i = 0, j = 0; i < n; i ++) {
            while (w[j][0] != w[i][0]) {
                if (g.size() == f[j]) g.push_back(w[j][1]);
                else g[f[j]] = min(g[f[j]], w[j][1]);
                j ++;
            }
            int l = 0, r = g.size() - 1;
            while (l < r) {
                int m = l + r + 1 >> 1;
                if (w[i][1] > g[m]) l = m;
                else r = m - 1;
            }
            f[i] = r + 1;
            ans = max(ans, f[i]);
        }
        return ans;
    }
};
编辑于 2021-02-17 09:39:22 回复(0)
用例太少了,我提交的一个有错误的代码,居然也能过。😂
发表于 2021-02-07 23:25:42 回复(0)
不符合时间复杂度要求 就当一种参考啦 留着自己复习用
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)
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param letters intvector<vector<>> 
     * @return int
     */
    static bool cmp(const vector<int> a,const vector<int> b)
    {
        if(a[0]==b[0])
            return a[1]>=b[1];//宽度相等时按照高度降序排列
        else
            return a[0]<b[0];//按照宽度升序排列
    }
    int LIS(vector<int> vec,int n)//经典的最长上升子序列问题,当然还可用二分优化
    {
        vector<int> dp(n,0);
        dp[0]=1;
        for(int i=1;i<n;i++)
        {
            for(int j=0;j<i;j++)
            {
                if(vec[i]>vec[j])
                    dp[i]=max(dp[i],dp[j]);
            }
            dp[i]++;
        }
        return *max_element(dp.begin(),dp.end());
    }
    int maxLetters(vector<vector<int> >& letters) {
        // write code here
        int n=letters.size();
        sort(letters.begin(),letters.end(),cmp);//排序
        vector<int> height;
        for(int i=0;i<n;i++)
        {
            height.push_back(letters[i][1]);
        }
        int res=LIS(height,n);//按照高度最长上升子序列
        return  res;
    }
};
发表于 2021-01-23 02:23:11 回复(0)