LeetCode 354. 俄罗斯套娃信封问题

ゝ一世哀愁。 2022-11-05 06:27 112阅读 0赞

给定一些标记了宽度和高度的信封，宽度和高度以整数对形式 (w, h) 出现。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。

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

说明:  
不允许旋转信封。

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

class Solution {
        
        public int maxEnvelopes(int[][] envelopes) {
        
            int res=1;
            //将信封按照第一维（宽度）进行排序
            Arrays.sort(envelopes,new Comparator<int[]>() {
        
            	@Override
            	public int compare(int[] o1, int[] o2) {
        
            		if (o1[0]==o2[0]) return o1[1]-o2[1];
            		return o1[0]-o2[0];
            	}
            });
         //   System.out.print(envelopes);
            int cnt[]=new int[envelopes.length];
            for(int i=0;i<envelopes.length;i++) {
        
            	System.out.println(envelopes[i][0]+" "+envelopes[i][1]);
            	cnt[i]=1;
            }
            for(int i=1;i<envelopes.length;i++) {
        
            	for(int j=0;j<i;j++) {
        
            		if(envelopes[i][0]>envelopes[j][0]&&envelopes[i][1]>envelopes[j][1])
            		cnt[i]=Math.max(cnt[i], cnt[j]+1);
            	}
            	res=Math.max(res, cnt[i]);
            }
            return res;
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，112人围观）

还没有评论，来说两句吧...

相关阅读

相关 JAVA函数套娃的骚操作

JAVA高级函数套娃的骚操作在项目代码中发现一个骚操作，2个高级函数套起来使用,一开始有点迷糊，后来写了个单测跑了下明了了。function的结果作为convertFun...

偏执的太偏执、/ 2024年04月22日 06:37/ 0 赞/ 65 阅读

相关 Java中的方法递归（套娃检索）

前言必读 > [读者手册（必读）\_云边的快乐猫的博客-CSDN博客][-CSDN] 1.什么是方法递归？答：方法自己调用自己。 2.递归存在的问题？答：如果

雨点打透心脏的1/2处/ 2023年09月27日 08:14/ 0 赞/ 113 阅读

相关 LeetCode 354. 俄罗斯套娃信封问题

给定一些标记了宽度和高度的信封，宽度和高度以整数对形式 (w, h) 出现。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。

ゝ一世哀愁。/ 2022年11月05日 06:27/ 0 赞/ 113 阅读

相关 LeetCode354. 俄罗斯套娃信封问题

给定一些标记了宽度和高度的信封，宽度和高度以整数对形式 (w, h) 出现。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。

╰+哭是因爲堅強的太久メ/ 2022年11月05日 06:27/ 0 赞/ 155 阅读

相关信封嵌套问题

/ 给出一些信封，每个信封用宽度和高度的整数对形式(w,h)表示，当一个信封的宽度和高度都比另外一个信封大的时候，那么就可以放进去，请计算最多能套几层？二维最

梦里梦外;/ 2022年10月29日 10:27/ 0 赞/ 145 阅读

相关序列型动态规划——俄罗斯套娃信封问题

给定一些标记了宽度和高度的信封，宽度和高度以整数对形式 (w, h) 出现。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。

悠悠/ 2022年10月27日 06:29/ 0 赞/ 168 阅读

相关 354. 俄罗斯套娃信封问题

链接：[https://leetcode-cn.com/problems/russian-doll-envelopes/][https_leetcode-cn.com_prob

爱被打了一巴掌/ 2022年08月28日 15:52/ 0 赞/ 141 阅读

相关俄罗斯信封问题

俄罗斯信封问题：一个信封有长和宽，规定，A信封如果长和宽都大于B信封，那么B信封可以放在A的里面。给你一个信封对象的数组，问，最多能套几层。 O(N\l

分手后的思念是犯贱/ 2022年06月08日 04:40/ 0 赞/ 187 阅读

相关 leetcode 354. Russian Doll Envelopes 俄罗斯套娃 + 动态规划DP + 类似LISS最长递增子序列的做法

You have a number of envelopes with widths and heights given as a pair of integers (w, h

青旅半醒/ 2022年06月07日 02:45/ 0 赞/ 145 阅读

相关 LeetCode56.合并区间、354. 俄罗斯套娃信封问题（合并区间进阶）

LeetCode56.合并区间【题目】给出一个区间的集合，请合并所有重叠的区间。【示例】输入: [[1,3],[2,6],[8,10],[15,18

╰+攻爆jí腚メ/ 2021年09月21日 06:16/ 0 赞/ 306 阅读