题解 | #信封嵌套问题#

题意整理

• 给定n个信封。
• 将长和宽较大的信封套在长和宽较小的信封上（必须严格大于）。

方法一（动态规划）

1.解题思路

当信封长度从小到大排列的时候，我们只需要让对应的宽度也从小到大就能完成信封嵌套，而让宽度从小到大排列，可以转化为求宽度序列的最长递增子序列。但是如果信封长度相同，宽度如何处理呢？
如果长度相同，宽度从小到大排列，那所求的递增子序列在长度相同时，可能会选两个宽度，这样就不能完成嵌套。所以我们可以在长度相同时，让宽度从大到小排列，这种情况下，相同长度，只能选一个宽度。

• 状态定义： 表示以索引i结束的最长递增子序列长度
• 状态初始化：将所有可能的序列长度初始化为1
• 状态转移：如果某个之前的宽度小于当前宽度，子序列就有可能从j跳到i,要么最长的序列是从j跳到i，要么就是它本身，所以 。

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param letters int二维数组 
     * @return int
     */
    public int maxLetters (int[][] letters) {
        //首先按信封长度升序排列，如果长度相等，按宽度降序
        Arrays.sort(letters,(o1,o2)->o1[0]==o2[0]?o2[1]-o1[1]:o1[0]-o2[0]);

        //求宽度序列的最长上升子序列
        int n=letters.length;
        int[] dp=new int[n];
        //初始化所有的情况为1
        Arrays.fill(dp,1);
        for(int i=1;i<n;i++){
            for(int j=0;j<i;j++){
                //如果某个之前的宽度小于当前宽度，子序列就有可能从j跳到i
                if(letters[j][1]<letters[i][1]){
                    dp[i]=Math.max(dp[i],dp[j]+1);
                }
            }
        }
        //返回dp数组中的最大元素
        return Arrays.stream(dp).max().orElse(-1);
    }
}

3.复杂度分析

• 时间复杂度：循环体总共进行了 次，所以时间复杂度是 。
• 空间复杂度：需要额外大小为n的dp数组，所以空间复杂度为 。

方法二（二分+维护单调递增序列）

1.解题思路

• 由方法一的分析可知，只要对letters进行排序预处理，就可以转化为一个最长递增子序列问题。
• 首先维护一个单调递增的子序列，子序列存放在tail数组里，当tail数组为空或者所有元素小于当前宽度时，直接将当前宽度放到tail数组末尾；如果当前宽度小于tail数组末尾元素，要考虑放到一个合适的位置（如果当前宽度target已经在tail数组中，直接放在原位置，否则放在恰好大于target的位置），使得tail数组尽可能长。最终tail数组的长度即为信封嵌套的层数。

动图展示：

2.代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param letters int二维数组 
     * @return int
     */
    public int maxLetters (int[][] letters) {
        //首先按信封长度升序排列，如果长度相等，按宽度降序
        Arrays.sort(letters,(o1,o2)->o1[0]==o2[0]?o2[1]-o1[1]:o1[0]-o2[0]);

        //维护一个单调递增的tail数组
        int[] tail=new int[letters.length];
        int end=-1;
        for(int[] letter:letters){
            int target=letter[1];
            //如果tail数组为空，或者所有元素小于target，直接加在末尾
            if(tail[0]==0||tail[end]<target){
                tail[++end]=target;
            }
            //如果target不大于tail数组最大值，找到它在tail数组的索引
            else{
                int index=binarySearch(tail,end,target);
                tail[index]=target;
            }
        }
        return end+1;
    }

    //二分查找target在tail数组0到end之间的索引，如果不存在，取第一个大于target的位置
    private int binarySearch(int[] tail,int end,int target){
        int l=0,r=end;
        while(l<r){
            int mid=l+(r-l)/2;
            if(tail[mid]>=target){
                r=mid;
            }
            else{
                l=mid+1;
            }
        }
        return l;
    }
}

3.复杂度分析

• 时间复杂度：排序的时间复杂度是 ，二分的时间复杂度，需要进行n次二分搜索，所以最终的时间复杂度是。
• 空间复杂度：需要额外大小为n的tail数组，所以空间复杂度为 。