俄罗斯套娃题库

俄罗斯套娃信封问题

给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。

当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。

请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。

注意：不允许旋转信封。

示例1:

输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出：3
解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。

示例2:

输入：envelopes = [[1,1],[1,1],[1,1]]
输出：1

整体思路:

• 首先我们将所有的信封按照 w 值第一关键字升序、h 值第二关键字降序进行排序；
• 随后我们就可以忽略 w 维度，求出 h 维度的最长严格递增子序列，其长度即为答案。

方案A 动态规划

思路:

:::details 点击查看代码

function maxEnvelopes(envelopes) {
    envelopes.sort((a,b)=>{
        if(a[0]!=b[0]){
            return a[0]-b[0];
        }else{
            return b[1]-a[1];
        }
    });
    const dp=new Array(envelopes.length).fill(1);
    let maxLength=0;
    for(let i=0;i<envelopes.length;i++){
        for(let j=0;j<i;j++){
            if(envelopes[i][1]>envelopes[j][1]){
                dp[i]=Math.max(dp[i],dp[j]+1);
            }
        }
        maxLength=Math.max(dp[i],maxLength);
    }
    return maxLength
};

:::

性能分析:

• 时间复杂度：O(n^2)，其中 n 是数组 envelopes 的长度，排序需要的时间复杂度为 O(nlogn)，动态规划需要的时间复杂度为 O(n^2)，前者在渐近意义下小于后者，可以忽略。

• 空间复杂度：O(n)，即为数组 f 需要的空间。

方案B 贪心+二分

:::details 点击查看代码

function maxEnvelopes(envelopes) {
    envelopes.sort((a,b)=>{
        if(a[0]!=b[0]){
            return a[0]-b[0];
        }else{
            return b[1]-a[1];
        }
    });
    const tail=new Array(envelopes.length).fill(0);
    let result=0;
    for(let item of envelopes){
        let start=0;
        let end=result;
        while(start<end){
            let middle=Math.floor((start+end)/2);
            if(tail[middle]<item[1]){
                start=middle+1;
            }else{
                end=middle;
            }
        }
        tail[start]=item[1];
        if(result==end){
            result++
        }
    }
    return result;
};

:::

性能分析:

• 时间复杂度：O(nlogn)，其中 n 是数组 envelopes 的长度，排序需要的时间复杂度为 O(nlogn)，动态规划需要的时间复杂度同样为 O(nlogn)。

• 空间复杂度：O(n)，即为数组 f 需要的空间。