2020年3月17日 完美世界笔试题2 俄罗斯套娃信封问题

问题

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

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

说明:
不允许旋转信封。

示例:

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

想法

• 先按w从小到大进行排序，当w相同时，按h从大到小排序。然后求解b的最长递增子序列。
• 然后将比较w,将其转化为一个最长子序列问题

例如

• envelopes = [[5,4],[6,4],[6,7],[2,3]]
• 排序后为 【2，3】，【5，4】，【6，7】，【6，4】
• 比较w,将其转化为一个最长子序列问题
• 就可以得到[2,3] => [5,4] => [6,7]

 public int maxEnvelopes(int[][] envelopes) {
            if(envelopes == null || envelopes.length == 0 || envelopes[0].length == 0)return 0;
            Arrays.sort(envelopes,new Comparator<int[]>() {
                @Override
                public int compare(int[] o1, int[] o2) {
                    if(o1[0] == o2[0])return o2[1] - o1[1];
                    return o1[0] - o2[0];
                }
            });

            int[] dp = new int[envelopes.length];
            dp[0] = 1;

            //用于记录最长的长度
            int max = 1;
            for (int i = 1; i < envelopes.length; i++) {
                dp[i] = 1;
                //遍历i之前的元素
                for (int j = i-1; j >= 0; j--) {
                    //如果递增的话
                    if (envelopes[i][1] > envelopes[j][1]) {
                        dp[i] = Math.max(dp[i],dp[j]+1);
                    }
                    max = Math.max(dp[i],max);

                }
            }
            return max;
        }