信封嵌套问题

梦里梦外; 2022-10-29 10:27 140阅读 0赞

/** * 给出一些信封，每个信封用宽度和高度的整数对形式(w,h)表示，当一个信封的宽度和高度都比另外一个信封大的时候，那么就可以放进去， * 请计算最多能套几层？ * 二维最长递增子序列问题 */
    public class Solution5 { 
    
        public static void main(String[] args) { 
            int[][] nums = new int[][]{ { 1,8},{ 2,3},{ 5,4},{ 5,2},{ 6,7},{ 6,4}};
            System.out.println(maxNum(nums));
        }
        static int maxNum(int[][] nums) { 
            Arrays.sort(nums, new Comparator<int[]>() { 
                @Override
                public int compare(int[] o1, int[] o2) { 
                    return o1[0] == o2[0] ? o2[1] - o1[1] : o1[0] - o2[0];
                }
            });
            int[] height = new int[nums.length];
            for (int i = 0; i < nums.length; i++) { 
                height[i] = nums[i][1];
            }
            return LIS(height);
        }
        /** dp[i]表示以height[i]结尾的最长递增子序列的长度*/
        static int LIS(int[] height) { 
            int[] dp = new int[height.length];
            // base case
            Arrays.fill(dp, 1);
            for (int i = 0; i < height.length; i++) { 
                for (int j = 0; j < i; j++) { 
                    if (height[i] > height[j]) { 
                        dp[i] = Math.max(dp[i], dp[j] + 1);
                    }
                }
            }
            int res = Integer.MIN_VALUE;
            for (int i = 0; i < dp.length; i++) { 
                res = Math.max(res, dp[i]);
            }
    
            return res;
        }
    }

发表评论取消回复

表情：

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

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

相关阅读

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

题目来源 [354. 俄罗斯套娃信封问题 - 力扣（LeetCode）][354. _ - _LeetCode] 题目描述给你一个二维整数数组 envelope

野性酷女/ 2023年09月23日 15:41/ 0 赞/ 110 阅读

相关牛客信封嵌套问题

题目链接：[https://www.nowcoder.com/practice/9b9fe43a92b74408988e20331b10f6b4?tpId=101&tqId=3

谁借莪１个温暖的怀抱￠/ 2023年06月04日 14:54/ 0 赞/ 58 阅读

相关 c语言信封比大小,从C打印信封＃

我试图做一个应用程序，将打印信封(自定义和正常)。 Im设置要打印的大小和页面，但当即时打印或查看打印预览时，页面大小仍然相同。基本上，该应用程序是3组合框(0：挑自定义大小，

女爷i/ 2023年01月22日 15:49/ 0 赞/ 177 阅读

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

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

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

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

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

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

相关信封嵌套问题

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

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

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

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

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

相关数字信封工作原理

数字信封是指发送方使用接收方的公钥来加密对称密钥后所得的数据，其目的是用来确保对称密钥传输的安全性。采用数字信封时，接收方需要使用自己的私钥才能打开数字信封得到对称密钥。

左手的ㄟ右手/ 2022年06月08日 10:08/ 0 赞/ 280 阅读

相关俄罗斯信封问题

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

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

相关数字信封

1.定义：数字信封是将对称密钥通过非对称加密(即:有公钥和私钥两个)的结果分发对称密钥的方法。数字信封是实现信息完整性验证的技术。（数字信封技术使用两层加密体系

本是古典何须时尚/ 2021年09月28日 09:20/ 0 赞/ 624 阅读