首页 > 试题广场 >

信封嵌套问题

[编程题]信封嵌套问题

热度指数：2369 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给n个信封的长度和宽度。如果信封A的长和宽都小于信封B，那么信封A可以放到信封B里，请求出信封最多可以嵌套多少层。

输入描述:

输出包含多行，第一行包括一个整数，代表信封的个数n。接下来n行，每行两个整数和，代表信封的长度和宽度。

输出描述:

输出包括一行，代表信封最多嵌套多少层。

示例1

输入

输出

说明

从里到外分别是{1，2}，{2，3}，{3，4}，{4，5}。

示例2

输入

2
1 4
4 1

输出

备注:

时间复杂度，空间复杂度。

算法知识视频讲解

查看答案及解析

Java

pein531

整体思路

排序+动态规划。大流程是：首先按照长度w从小到大，高度h从大到小对信封数组进行二次排序，然后再求高度的最长递增子序列。这么做的原因主要是：先对长度进行升序可以保证从左往右选信封时能够保证单调不减。但是我们又不能选择长度相同的信封进行嵌套，同一长度的信封在高度上的降序就是为了防止选择出两个长度相同的信封。也就是说，对于同一个长度的多个信封，你只能选择一个，这样就能保证你求得高度的最长递增子序列的同时，还能保证这些信封的长度也一定是严格递增的。

经典做法

排序就不多说了，这个题的重头戏是后面求最长递增子序列，但是经典的动态规划其时间复杂度为O(N²)，提交后会超时，代码如下：

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.Comparator;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] pairs = new int[n][2];
        for(int i = 0; i < n; i++){
            String[] params = br.readLine().split(" ");
            pairs[i][0] = Integer.parseInt(params[0]);
            pairs[i][1] = Integer.parseInt(params[1]);
        }
        System.out.println(maxEnvelopes(pairs));
    }
    
    private static int maxEnvelopes(int[][] envelopes) {
        if (envelopes.length == 0) return 0;
        int n = envelopes.length;
        // 按w升序，按h降序，然后求h的最长上升子序列
        Arrays.sort(envelopes, new Comparator<int[]>() {
            public int compare(int[] e1, int[] e2) {
                if (e1[0] != e2[0])
                    return e1[0] - e2[0];
                else
                    return e2[1] - e1[1];
            }
        });
        // 这样就不可能在一个宽度值中选择到两个不同h的信封
        int[] dp = new int[n];
        // dp[i]表示在选择信封i的情况下，前i个信封所构成的最长上升序列长度
        Arrays.fill(dp, 1);
        int maxLen = 1;
        for(int i = 1; i < n; i++){
            for(int j = 0; j < i; j++){
                if(envelopes[j][1] < envelopes[i][1]) {
                    // 此时就可以在dp[j]的基础上选择第i个信封，信封数+1，尝试前面不同的j，看哪个能使dp[i]最大
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            // 确定了dp[i]的值，更新dp数组的最大值
            maxLen = Math.max(maxLen, dp[i]);
        }
        return maxLen;
    }
}

整体思路是尝试每个高度作为结尾时能够获得的最长递增子序列长度，但是对于某一个高度envelopes[i][1]，我们需要把它接在一个小于它高度的信封envelopes[j]（j<i）后面，并且信封j必须是所有高度小于信封i的信封中dp[j]最大的那个。要把它找出来的话我们就必须对i的左边进行穷举，从而使得算法的时间复杂度过高。

算法优化

要想避免这个穷举的过程，我们需要构建出单调性，只要构建出单调性，我们就可以使用二分，把O(N)穷举的时间复杂度降低至O(logN)。这里我们增加一个辅助数组ends，数组中填过数的区域表示有效区域，有效区域中的元素ends[i]表示长度为i+1的最长递增子序列中的最小结尾。很显然这个ends数组是个单调递增的数组，因为每个位置都是给定长度下的最小结尾，如果长度L₂>L₁，那么更长的最长递增子序列的结尾一定比短的那个子序列的最小结尾大。所以当我们遍历到信封i时，就可以在ends数组的有效区域内进行二分查找，寻找第一个大于等于envelopes[i][1]的位置，如果找到了位置x，说明envelopes[i][1]应该作为长度为x+1的最长递增子序列的更小结尾放在此处；如果没找到就直接将envelopes[i][1]放在ends数组有效区域的下一个位置，表示此时添加上信封i，能够使得最长递增子序列长度增加1，ends数组的有效区域扩充一个元素。

import java.lang.String;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.Comparator;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] pairs = new int[n][2];
        for(int i = 0; i < n; i++){
            String[] params = br.readLine().split(" ");
            pairs[i][0] = Integer.parseInt(params[0]);
            pairs[i][1] = Integer.parseInt(params[1]);
        }
        System.out.println(maxEnvelopes(pairs));
    }
    
    private static int maxEnvelopes(int[][] envelopes) {
        if(envelopes.length == 0) return 0;
        int n = envelopes.length;
        // 按w升序，按h降序，然后求h的最长上升子序列，这样就不可能在一个宽度值中选择到两个不同h的信封
        Arrays.sort(envelopes, new Comparator<int[]>() {
            public int compare(int[] e1, int[] e2) {
                if (e1[0] != e2[0])
                    return e1[0] - e2[0];
                else
                    return e2[1] - e1[1];
            }
        });
        int[] dp = new int[n];
        int[] ends = new int[n];
        dp[0] = 1;
        ends[0] = envelopes[0][1];
        int tail = 0;      // ends数组中有效区域的最后一个元素
        int maxLen = 1;
        for(int i = 1; i < n; i++){
            int index = lowerbound(ends, 0, tail, envelopes[i][1]);    // 寻找第一个h大于等于当前信封高度的位置
            if(index > tail){
                tail ++;
                ends[index] = envelopes[i][1];
            }else{
                ends[index] = envelopes[i][1];
            }
            dp[i] = index + 1;
            maxLen = Math.max(maxLen, dp[i]);
        }
        return maxLen;
    }
    
    private static int lowerbound(int[] arr, int L, int R, int target) {
        int left = L, right = R, idx = R + 1;
        while(left <= right){
            int mid = left + ((right - left) >> 1);
            if(arr[mid] < target){
                left = mid + 1;
            }else{
                idx = mid;
                right = mid - 1;
            }
        }
        return idx;
    }
}

这样通过二分查找，就将之前经典动态规划中对左边的枚举行为的时间复杂度O(N)降低至O(logN)，从而使得算法的整体达成题目要求的时间复杂度O(NlogN)，空间复杂度O(N)。

PS

后来发现用O(logN)的这个算法时，dp数组并没有什么用，因为ends数组本来就包含长度信息，ends[i]是长度为i+1的递增子序列的最小结尾，“下标+1”就是长度的信息。因此这个空间花费是可以省掉的。

编辑于 2021-12-11 15:45:52 回复(0)

提交观点

问题信息

动态规划排序

上传者：小小

难度：

1条回答 41收藏 5639浏览

通过挑战的用户

查看代码

牛客38959...

2023-02-16 15:11:16
开心的孤勇者在抱佛脚

2023-02-13 15:07:54
『戥』

2022-09-26 16:04:24
牛客14597...

2022-09-21 20:18:34
牛客17615...

2022-09-10 18:59:28