首页 > 试题广场 >

信封嵌套问题

[编程题]信封嵌套问题
  • 热度指数:4297 时间限制: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)。
经典的动态规划做法就不多说了,当确定以letters[i][1]结尾的序列时,要将它拼在之前最长的递增序列末尾。但是哪个序列最长?我们不得而知,因此会存在向数组左边遍历的行为,从而造成O(n2)的时间复杂度。
要把O(n2)的时间复杂度优化到O(nlog2n),一个直观的想法就是要把上面提到的遍历行为省掉,如此一来就需要构建单调性,利用二分查找来优化。这里我们弃用之前的dp数组,使用一个新的数组ends,数组中填过数的区域表示有效区域,有效区域中的元素ends[i]表示长度为i+1的最长递增子序列中的最小结尾。很显然这个ends数组是个单调递增的数组,因为每个位置都是给定长度下的最小结尾,如果长度L2>L1,那么更长的最长递增子序列的结尾一定比短的那个子序列的最小结尾大。所以当我们遍历到信封i时,就可以在ends数组的有效区域内进行二分查找,寻找第一个大于等于letters[i][1]的位置,如果找到了位置x,说明letters[i][1]应该作为长度为x+1的最长递增子序列的更小结尾放在此处;如果没找到就直接将letters[i][1]放在ends数组有效区域的下一个位置,表示此时添加上信封i,能够使得最长递增子序列长度增加1,ends数组的有效区域扩充一个元素。
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param letters int二维数组 
     * @return int
     */
    public int maxLetters (int[][] letters) {
        // write code here
        Arrays.sort(letters, (a, b) -> a[0] != b[0]? a[0] - b[0]: b[1] - a[1]);
        int n = letters.length;
        int[] ends = new int[n];       // ends[i]表示长度为i+1的递增子序列最小结尾
        ends[0] = letters[0][1];
        int maxLen = 1, tail = 0;      // 最长递增子序列长度与ends数组的有效区末尾下标
        for(int i = 1; i < n; i++){
            int index = lowerbound(ends, 0, tail, letters[i][1]);
            ends[index] = letters[i][1];
            if(index > tail){
                // ends数组的有效区没能找到第一个大于等于letters[i][1]的区域,就扩充ends数组有效区
                tail ++;
            }
            maxLen = Math.max(maxLen, index + 1);
        }
        return maxLen;
    }
    
    private 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;
    }
}

发表于 2021-12-11 09:40:47 回复(0)
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param letters intvector<vector<>> 
     * @return int
     */
    static bool cmp(vector<int>& a, vector<int>& b)
    {
        return a[0] < b[0] || (a[0] == b[0] && a[1] > b[1]);
    }
    int maxLetters(vector<vector<int> >& letters) {
        // write code here
        if(letters.empty())
            return 0;
        int n = letters.size();
        // 这一步是将二维转为一维问题
        sort(letters.begin(), letters.end(), cmp);
        // 下面的这个是求解 最长递增子数组
        vector<int> f(n, 1);
        for(int i=1; i<n; i++)
        {
            for(int j=0; j<i; j++)
            {
                if(letters[j][1] < letters[i][1])
                    f[i] = max(f[i], f[j] + 1);
            }
        }
        return *max_element(f.begin(), f.end());
    }
};

发表于 2022-09-05 11:52:35 回复(0)
package main

import "sort"

/**
 * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
 *
 * 
 * @param letters int二维数组 
 * @return int
*/
func maxLetters( letters [][]int ) int {
    n:=len(letters)
    sort.Slice(letters,func(i,j int)bool{
        return letters[i][0]<letters[j][0]
    })
    ans:=1
    dp:=make([]int,n)
    for i,lt:=range letters{
        dp[i]=1
        for j:=0;j<i;j++{
            if lt[0]>letters[j][0]&&lt[1]>letters[j][1]{
                dp[i]=max(dp[i],dp[j]+1)
            }
        }
        if ans<dp[i]{
            ans=dp[i]
        }
    }
    return ans
}

func max(a,b int)int{
    if a>b{
        return a
    }
    return b
}

发表于 2023-03-11 18:50:01 回复(0)
还是那个问题,为啥你的宽比长更长呢?
为什么标准解答都不考虑这个情况?
发表于 2022-09-13 00:20:36 回复(0)
先按宽度从小到大排序。在重载<运算符的时候当两者宽度相等时,故意规定长度大的视为更小,以免后续出现两个信封等宽度但长度不同的误算情况。剩下的就是根据信封长度,按复杂度nlogn的最长上升子序列算法问题处理。
class Solution {
private:
    struct letter {
        int width;
        int length;
        bool operator <(const letter& A) {
            if (width < A.width)
                return true;
            if (width > A.width)
                return false;
            if (length < A.length)
                return false;
            return true;
        }
        letter(int w, int l) :width(w), length(l) {}
    };
public:
    int maxLetters(vector<vector<int> >& letters) {
        int size = letters.size();
        letter** arr = new letter * [size]();
        for (int i = 0; i < size; ++i)
            arr[i] = new letter(letters[i][0], letters[i][1]);
        sort(arr, arr + size, [](letter* A, letter* B) {
            return *A < *B;
            });
        int* length = new int[size + 1]();
        int index = 1;
        length[1] = arr[0]->length;
        int temp;
        for (int i = 1; i < size; ++i) {
            temp = arr[i]->length;
            if (temp > length[index])
                length[++index] = temp;
            else if (temp < length[index]) {
                int left = 1, right = index;
                int mid;
                while (1) {
                    mid = left + right >> 1;
                    if (length[mid] > temp)
                        right = mid - 1;
                    else if (length[mid] < temp)
                        left = mid + 1;
                    else
                        break;
                    if (left > right) {
                        length[left] = temp;
                        break;
                    }
                }
            }
        }
        delete[]length;
        for (int i = 0; i < size; ++i)
            delete[]arr[i];
        delete[]arr;
        return index;
    }
};


发表于 2022-01-27 00:05:42 回复(0)
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param letters int二维数组 
     * @return int
     */
    public int maxLetters (int[][] letters) {
        // write code here
        Arrays.sort(letters, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if(o1[0]!=o2[0]){
                    return o1[0]-o2[0];
                }else{
                    return o2[1]-o1[1];
                }
            }
        });
        List<Integer> hs = new ArrayList<>();
        for(int i=0;i<letters.length;i++){
            int tmp = letters[i][1];
            if(hs.isEmpty()||hs.get(hs.size()-1)<tmp){
                hs.add(tmp);
            }else{
                int l = 0;
                int r = hs.size()-1;
                while(l<=r){
                    int mid = (l+r)/2;
                    if(hs.get(mid)<tmp){
                        l = mid+1;
                    }else{
                        if(mid==0||hs.get(mid-1)<tmp){
                            hs.set(mid,tmp);
                            break;
                        }else{
                            r = mid-1;
                        }
                    }
                }
            }
        }
        return hs.size();
    }
}

发表于 2021-08-20 13:04:15 回复(0)
这道题的思路是:
1:先排序,排序规则是:先长度升序,再宽度降序
2:再将宽度看为一维数组,求最大子序列,长度即为本题的最大嵌套信封;
import java.util.*;


public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param letters int二维数组
* @return int
*/
public int maxLetters (int[][] letters) {
// write code here
if(letters==null||letters.length<1){return 0;};
if(letters.length==1){return 1;};
Arrays.sort(letters,new Comparator<int[]>(){
@Override
public int compare(int[] o1,int[]o2){
if(o1[0]==o2[0]){
return o2[1]-o1[1];
}else{
return o1[0]-o2[0];
}
}
});
int[]dp =new int[letters.length];
dp[0]=1;
int maxNcoun=0;
for(int i=0;i<letters.length;i++){
int left=0,right=maxNcoun;
while(left<right){
int mid=(left+right)>>1;
if(dp[mid]>=letters[i][1]){
right=mid;
}else{
left=mid+1;
}
}
dp[left]=letters[i][1];
if(left==maxNcoun)maxNcoun++;
// maxNcoun=Math.max(maxNcoun,max);
}
return maxNcoun;
}
}


发表于 2021-08-13 23:17:47 回复(0)
public int maxLetters (int[][] letters) {

        Arrays.sort(letters, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0]== o2[0]) {
                    return o1[1] - o2[1];
                } else {
                    return o1[0] - o2[0];
                }
            }
        });
        int [] dp = new int[letters.length];
        dp[0] = 1;
        for (int i = 1;i < letters.length;i++) {
            for (int j = 0;j < i;j++) {
                if (letters[i][0] > letters[j][0] && letters[i][1] > letters[j][1]) {
                    dp[i] = Math.max(dp[i],dp[j] + 1);
                } else {
                    dp[i] = Math.max(dp[i],dp[j]);
                }
            }
        }

        return dp[letters.length - 1];
    }
发表于 2021-07-20 18:20:51 回复(0)

暴力递归

class Solution {
public:
    static bool cmp (const vector<int> a,const vector<int> b)
    {
        if(a[0]!=b[0])
            return a[0]<b[0];
        else
            return a[1]<b[1];
    }
    int process(vector<vector<int> >& letters, int len,int wide,int times,int index)
    {
        if(index==letters.size())
            return times;

        if(len>=letters[index][0] || wide>=letters[index][1])
            return process(letters,len,wide,times,index+1);
        // 要当前的信封
        int letterin=process(letters,max(len,letters[index][0]),max(wide,letters[index][1]),times+1,index+1);
        // 不要当前的信封
        int letterout=process(letters,len,wide,times,index+1);
        return max(letterin,letterout);
    }
    int maxLetters(vector<vector<int> >& letters) {
        // 首先对 lectters 排序
        sort(letters.begin(),letters.end(),cmp);
        int count = process(letters,0,0,0,0);
        return count;
    }
};
编辑于 2021-07-17 11:21:16 回复(0)
import java.util.*;

class Envelope {
    public int len;
    public int wid;
    public Envelope(int weight, int height) {
        this.len = weight;
        this.wid = height;
    }
}

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param letters int二维数组 
     * @return int
     */
    public int maxLetters (int[][] letters) {
        // write code here
        if (letters.length == 0 || letters[0].length == 0)
            return 0;
        Envelope[] env = getSortedEnvelopes(letters);
        int[] arr = new int[env.length];
        for (int i = 0; i < env.length; i++) {
            arr[i] = env[i].wid;
        }
        return getLongestSeq(arr);
    }
    
    //找arr中最长递增子序列
    public int getLongestSeq(int[] arr) {
        int[] dp = new int[arr.length];
        int[] ends = new int[arr.length];
        int right = 0;
        int l = 0;
        int mid = 0;
        int r = 0;
        dp[0] = 1;
        ends[0] = arr[0];
        int max = dp[0];
        for (int i = 0; i < arr.length; i++) {
            l = 0;
            r = right;
            while (l <= r) {
                mid = (l+r) / 2;
                if (arr[i] > ends[mid])
                    l = mid + 1;
                else
                    r = mid - 1;
            }
            if (r == right)
                right++;
            ends[l] = arr[i];
            dp[i] = l+1;
            max = Math.max(max, dp[i]);
        }
        return max;
    }
    
    
    public class EnvelopeComparator implements Comparator<Envelope> {
        @Override
        public int compare(Envelope o1, Envelope o2) {
            //为了避免长度相同的情况下,宽度小的被宽度大的误认为可以嵌套
            //换句话说,按这个排列,但看宽度数组,如是你想宽度比我小,除非你长度比我小
            //否则长度若一样,前面的宽度肯定比后面的宽度大
            return o1.len != o2.len ? o1.len - o2.len : o2.wid - o1.wid;
        }
    }
    
    public Envelope[] getSortedEnvelopes (int[][] matrix) {
        Envelope[] res = new Envelope[matrix.length];
        for (int i = 0; i < matrix.length; i++) {
            res[i] = new Envelope(matrix[i][0], matrix[i][1]);
        }
        Arrays.sort(res, new EnvelopeComparator());
        return res;
    }
}

发表于 2021-07-16 20:43:24 回复(0)
class Solution {
    public:
    
    static bool cmp(vector<int>&a,vector<int>&b){
        if(a[0]!=b[0]) return a[0]<b[0];
        else return a[1]>b[1];
    }

    int maxLetters(vector<vector<int> >& letters) {
        /*
            letters的第一列理解为长度 第二列理解为宽度
            先按长度升序 当长度相同时宽度降序
            便于后边求解LIS
        */
        sort(letters.begin(), letters.end(), cmp); 
        vector<int> b; //存取宽度数据 
        for (int i = 0; i < letters.size(); i++) {
            b.push_back(letters[i][1]);
        }

        //贪心+二分求解最长递增子序列长度
        vector<int> res; //遍历宽度的过程中的贪心LIS
        res.push_back(b[0]); //第一个宽度总可以无条件放进来
        int maxl = 0; //遍历中更新的LIS长度
        for(int i = 1; i < b.size(); i++) {
            if (b[i] > res.back()) {
                res.push_back(b[i]);
            }else {
                int pos = lower_bound(res.begin(), res.end(), b[i]) - res.begin(); //二分
                res[pos] = b[i];
            }
        }
        maxl = res.size(); //最后贪心res长度就是LIS的长度 贪心 总是局部最优嘛
        return maxl;
    }
};

发表于 2021-07-02 10:30:13 回复(0)
套娃分析:
使用动态规划,假设dp[i]为第i个信封套在最外面的套娃数目

扫描整个数组,如果某个信封能被我套住,
例如 j 能被 i 套住,那么 dp[i]>=dp[j]+1必然成立,更新dp[i] 的数值。
固定i的情况下,扫描所有的j,用dp[j]更新dp[i]的数值。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param letters intvector<vector<>> 
     * @return int
     */
    int maxLetters(vector<vector<int> >& letters) {
        // 使用动态规划,假设dp[i]为第i个信封套在最外面的套娃数目
        int N=letters.size();
        int *dp=new int[N];
        for(int i=0;i<N;i++) dp[i]=1;
        
        // 替换次数
        int replace=0;
        do{
            replace=0;
            for(int i=0;i<N;i++){
                for(int j=0;j<N;j++){
                    if(j==i) continue;
                    if(letters[j][0]<letters[i][0] && letters[j][1]<letters[i][1] ){
                        if( dp[i]<dp[j]+1  ){
                            dp[i]=dp[j]+1;
                            replace+=1;
                        }
                    }
                }
            }
        }
        while(replace!=0);
        int maxdp=0;
        for(int i=0;i<N;i++){
            if(dp[i]>maxdp) maxdp=dp[i];
        }
        return maxdp;
    }
};


编辑于 2021-06-08 21:17:52 回复(0)
class Solution:
    def maxLetters(self , letters ):
        # write code here
        # 其实第一个肯定能套进去。
        result = 1
        pre = 0
        letters = sorted(letters, key = lambda x:(x[0],x[1]))
        for i in range(1, len(letters)):
            if letters[i][0] > letters[pre][0] and letters[i][1] > letters[pre][1]:
                result += 1
                pre = i
        return result

发表于 2021-06-02 17:59:59 回复(0)
import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param letters int二维数组 
     * @return int
     */
    int res3 = 0;
    int cur = 0;
    public int maxLetters (int[][] letters) {
        // write code here
        int[] dp = new int[letters.length];
        for (int i = 0; i < letters.length; i++) {
            dfs(letters, dp,  i , letters[i][0], letters[i][1], 1, true);
            dp[i] = cur;
        }
        return res3;
    }

    public void dfs(int[][] letters, int[] dp, int cur, int length, int width,  int size, boolean flag) {
        for (int i = 0; i < letters.length; i++) {
            if (letters[i][0] < length && letters[i][1] < width){
                if (dp[i] != 0) {
                    size += dp[i];
                    break;
                }
                flag = false;
                dfs(letters, dp, i, letters[i][0], letters[i][1], size + 1, true);
            }
        }
        if (flag) {res3 = Math.max(res3, size); cur = size;}
    }
}

发表于 2021-05-13 13:03:38 回复(0)
#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
# 
# @param letters int二维数组 
# @return int
#
class Solution:
    def maxLetters(self , letters ):
        letters.sort(key=lambda x: (x[0], -x[1]))
        w, h = 0, 0
        cnt = 0
        # 转换成最长递增子序列的问题了
        def bs(nums, target):
            # 找到第一个比target大的数,返回index
            l, r = 0, len(nums)-1
            while l < r:
                m = l + ((r-l)>>1)
                if nums[m] >= target:
                    r = m
                else:
                    l = m + 1
            return l if nums[l] >= target else l+1
        l = []
        for i in range(len(letters)):
            if not l&nbs***bsp;l[-1] < letters[i][1]:
                l.append(letters[i][1])
            else:
                idx = bs(l, letters[i][1])
                l[idx] = letters[i][1]
        return len(l)

发表于 2021-04-04 21:13:11 回复(0)
首先按照长的升序排序
然后求宽的最长升序子序列
import java.util.*;

public class Solution {
    public int maxLetters (int[][] letters) {
        // write code here
        if(letters.length == 0) return 0;
        Arrays.sort(letters, new Comparator<int[]>(){
            public int compare(int[] a, int[] b){
                if(a[0] == b[0]) return a[1] - b[1];
                else return a[0] - b[0];
            }
        });
        int n = letters.length;
        int[] dp = new int[n];
        dp[0] = 1;
        for(int i = 1; i < n; i++){
            for(int j = 0; j < i; j++){
                if(letters[i][1] > letters[j][1])
                    dp[i] = Math.max(dp[i], dp[j]);
            }
            dp[i]++;
        }
        return dp[n - 1];
    }
}


发表于 2021-03-23 16:11:00 回复(1)

动态规划+二分查找
时间复杂度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)