信封嵌套问题

梦里梦外; 2022-10-29 10:27 106阅读 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 条评论，106人围观）

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

相关阅读

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

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

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

相关牛客信封嵌套问题

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

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

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

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

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

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

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

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

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

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

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

相关信封嵌套问题

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

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

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

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

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

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

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

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

相关俄罗斯信封问题

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

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

相关数字信封

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

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