首页 > 试题广场 >

信封嵌套问题

[编程题]信封嵌套问题

热度指数：2391 时间限制：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)

AnnaSophia_Robb

#include<bits/stdc++.h>
using namespace std;

struct Node{
    int length;
    int width;
};
bool comp(Node a,Node b){
    return a.length == b.length ? a.width > b.width : a.length < b.length;
}
int main(){
    int n; cin >> n;
    vector<Node> arr(n);
    for(int i=0; i<n; i++) cin>>arr[i].length>>arr[i].width;
    sort(arr.begin(),arr.end(),comp);
    vector<int> dp;
    int k=0;
    dp.push_back(arr[0].width);
    for(int i=1; i<n; i++){
        if(arr[i].width > dp.back())
            dp.push_back(arr[i].width);
        else{
            auto it = upper_bound(dp.begin(),dp.end(),arr[i].width);
            *it = arr[i].width;
        }
    }
    cout << dp.size();
}

发表于 2020-02-26 22:00:42 回复(2)

C/C++

nbgao

#include <bits/stdc++.h>
using namespace std;

struct P{
    int x, y;
};

bool cmp(P a, P b){
    // if(a.x==b.x)
    //     return a.y<b.y;
    return a.x>b.x;
}

int main(){
    int n, x, y, Max=0;
    cin>>n;
    P p[n];
    for(int i=0;i<n;i++){
        cin>>x>>y;
        p[i] = P{x,y};
    }
    sort(p, p+n, cmp);
    int b[n];
    b[0] = p[0].y;
    for(int i=1;i<n;i++){
        int l=0, r=Max, m=0;
        while(l<=r){
            m = (l+r)>>1;
            if(b[m]>p[i].y)
                l = m+1;
            else
                r = m-1;  
        }
        Max = max(Max, l);
        b[l] = p[i].y;
    }
    cout<<Max+1<<endl;
    return 0;
}

发表于 2020-02-21 00:21:23 回复(1)

helloxuanbao

#include <stdio.h>
#include <stdlib.h>

#define max(a, b) ((a) > (b) ? (a) : (b))

typedef struct {
    int len;
    int wid;
} Envelope;

int compare(void *v1, void *v2) {
    Envelope *e1 = (Envelope *) v1;
    Envelope *e2 = (Envelope *) v2;
    return (e1->len != e2->len) ? (e1->len - e2->len) : (e2->wid - e1->wid);
}

int main(void) {
    int n, len, wid;
    scanf("%d", &n);
    Envelope *envs = (Envelope *) malloc(sizeof(Envelope) * n);
    Envelope e;
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &len, &wid);
        *(envs + i) = (Envelope) {len, wid};
    }
    qsort(envs, n, sizeof(Envelope), compare);
    int *ends = (int *) malloc(sizeof(int) * n);
    int right = 0, l, r, mid;
    ends[0] = envs[0].wid;
    for (int i = 1; i < n; i++) {
        l = 0, r = right;
        while (l <= r) {
            mid = (l + r) >> 1;
            if (ends[mid] < envs[i].wid) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        right = max(right, l);
        ends[l] = envs[i].wid;
    }
    printf("%d\n", right + 1);
    return 0;
}

发表于 2022-01-28 15:36:10 回复(0)

FrankChan

这道题的有趣之处在于，按宽度对信封排序后，问题就变成了求序列中以高为准的最大递增子序列的长度。

#include <iostream>
(720)#include <vector>
#include <algorithm>
using namespace std;

struct rec {//信封
    int w; 
    int h;
    rec(int ww, int hh):w(ww), h(hh){}; 
    bool operator < (const rec& other) const {
        return w < other.w;
    }
};

int maxLevels(vector<rec>& recs) {
    int n = recs.size();
    sort(recs.begin(), recs.end());//按宽度排序，问题就变成求高的最长递增子序列长度
    vector<int> ends(n);
    ends[0] = recs[0].h; //ends[i]表示以长度为i+1的关于信封高的递增子序列的最小结束元素
    int right = 0; //ends的有效范围，最后的结果+1表示最长递增子序列长度
    int l = 0, r= 0; //二分查找的范围
    for(int i = 1; i < n; i++) {
        l = 0;
        r = right;
        while(l <= r) {//查找recs[i].h在ends中的插入位置
            int mid = (l + r) >> 1;
            if(recs[i].h > ends[mid]) {
                l = mid + 1;
            }
            else {
                r = mid - 1;
            }
        }
        right = max(right, l); //ends范围可能更新
        ends[l] = recs[i].h; 
    }
    return right + 1;
}
int main() {
    int n;
    int w, h;
    cin >> n;
    vector<rec> recs;
    for(int i = 0; i < n; i++) {
        cin >> w >> h;
        rec curRec = rec(w, h);
        recs.push_back(curRec);
    }
    cout << maxLevels(recs) << endl;
    return 0;
}

发表于 2020-04-21 03:06:43 回复(0)

我要收offer

//先按照长递增排序，然后长度相同的按照宽递减排序，最后按照宽去找到最长递增子序列。
import java.io.*;
import java.util.*;
public class Main{
   	 public static void main(String []args)throws IOException{
	        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
	        int n = Integer.parseInt(bf.readLine().trim());
	        int[][] arr = new int[n][2];
	        for(int i = 0; i< n; i++){
	            String[] str = bf.readLine().trim().split(" ");
	            arr[i][0] = Integer.parseInt(str[0]);
	            arr[i][1] = Integer.parseInt(str[1]);
	        }
	        bf.close();
	        Arrays.sort(arr, (o1, o2) -> (o1[0]-o2[0] != 0 ? o1[0]-o2[0] : o2[1] - o1[1]));
	        //二分查找法计算LIS长度，该方法在前面一题LIS的讨论区有详细介绍
	        int[]minTail = new int[n];
	        int len = 0;
	        for(int i = 0;i<n;i++){
	            int index = Arrays.binarySearch(minTail, 0, len, arr[i][1]);
	            if(index < 0){
	                index = -index -1;
	            }
	            
	            minTail[index] = arr[i][1];
	            
	            if(index == len)
	                len++;
	        }
	        System.out.println(len);
	    }
}

发表于 2019-09-23 18:02:12 回复(0)

C++

麦芒2021

#include "bits/stdc++.h"

using namespace std;

/*
思路：
先按照第一个维度从小到大排序，一样时第二个维度从小到大
然后按照第二个维度求最大递增子序列
然后取出第一个维度相等的情况
*/
bool cmp(vector<int>& a,vector<int>& b){
    if(a[0]==b[0]) return a[1]<b[1];
    return a[0]<b[0];
}
int midsearch(vector<vector<int>>& letter,vector<int>& dp,int target){
    int left=0,right=dp.size();
    int mid;
    while(left<right){
        mid=(left+right)>>1;
        if(letter[dp[mid]][1]==target) return mid;
        else if(letter[dp[mid]][1]<target) left=mid+1;
        else right=mid;
    }
    return left;
}
int main(){
    int len;
    cin>>len;
    vector<vector<int>> letter(len,vector<int>(2,0));
    for(int i=0;i<len;i++)cin>>letter[i][0]>>letter[i][1];
    sort(letter.begin(),letter.end(),cmp);
    int ret=0;
    vector<int> dp;
    dp.push_back(0);
    for(int i=1;i<len;i++){
        if(letter[i][1]>letter[dp.back()][1]) 
            dp.push_back(i);
        else {
            int tmp=midsearch(letter,dp,letter[i][1]);
            dp[tmp]=i;
        }
    }
    ret=dp.size();
    for(int i=1;i<dp.size();i++){
        if(letter[dp[i]][0]==letter[dp[i-1]][0]) ret--;
    }
    cout<<ret;
    return 0;
}

发表于 2022-07-16 23:56:35 回复(0)

阿巍十八式

import sys
import bisect
 
def parse(array, length):
    array.sort(key=lambda x:(x[0],-x[1]))
    array = [vl[1] for vl in array]
    ends = [array[0]]

    for idx in range(1, length):
        if array[idx] > ends[-1]:
            ends.append(array[idx])
        else:
            l = bisect.bisect_left(ends, array[idx])
            ends[l] = array[idx]
    return len(ends)

n = int(sys.stdin.readline().strip())
values = [list(map(int, sys.stdin.readline().strip().split())) for _ in range(0, n)]
out = parse(values, n)
print(out)

根据楼上老哥的代码，稍微修改了下，自己写的是二分查找一直没AC 不知道是不是边界没处理好。

发表于 2020-09-19 13:41:09 回复(0)

字节bug跳动

import sys
import functools
import bisect



def parse(array, length):

    array = sorted(array,
                   key=functools.cmp_to_key(
                       lambda a, b:
                       a[0] - b[0] + int(a[0] == b[0]) * (-a[1] + b[1])
                   ))

    array = [vl[1] for vl in array]

  
    ends = [array[0]]

    for idx in range(1, length):
        if array[idx] > ends[-1]:
            ends.append(array[idx])
      
        else:
            l = bisect.bisect_left(ends, array[idx])
            ends[l] = array[idx]
     

    return len(ends)


n = int(sys.stdin.readline().strip())
values = [list(map(int, sys.stdin.readline().strip().split())) for _ in range(0, n)]
out = parse(values, n)
print(out)

编辑于 2020-08-17 21:24:11 回复(0)

世界上的一道风

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

int countLetter(const vector<int> &width)
{
vector<int> table;
for (int i = 0; i < width.size(); ++i)
{
auto it = lower_bound(table.begin(), table.end(), width[i]);
if (it == table.end()) table.push_back(width[i]);
else
*it = width[i];
}
return table.size();
}

int main()
{
int N; cin >> N;
multimap<int, int> table;
int a, b;
for (int i = 0; i < N; i++)
{
cin >> a >> b;
table.insert(make_pair(a, b));
}
vector<int> width;
for (auto it = table.begin(); it != table.end(); ++it)
{
width.push_back(it->second);
}
cout << countLetter(width);
}

发表于 2019-08-31 10:10:03 回复(0)

BetyDancer内推

解题思路：先按着信封的长度排序，然后能否嵌套就看信封的宽度了，将该问题转为最长递增子序列问题。

import java.util.*;
public class Main{
    public static void main(String [] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int [][] arr = new int [n][2];
        for(int i=0;i<n;i++){
            arr[i][0]=sc.nextInt();
            arr[i][1]=sc.nextInt();            
        }
        Arrays.sort(arr,(x,y)->(y[0]-x[0]));
        int ends []= new int [n];
        ends[0]= arr[0][1];
        int left =0;
        int right=0;
        int len =0;
        int mid =0;
        for(int i=1;i<n;i++){
            left=0;
            right=len;
            while(left<=right){
                mid = left+(right-left)/2;
                if(ends[mid]>arr[i][1]){
                    left=mid+1;
                }else{
                    right=mid-1;
                }
            }
            len=Math.max(len,left);
            ends[left]=arr[i][1];
        }
        System.out.println(len+1);
            
    }
}

发表于 2019-08-15 10:03:40 回复(2)

提交观点

问题信息

动态规划排序

上传者：小小

难度：

11条回答 41收藏 7484浏览

通过挑战的用户

查看代码

牛客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