俄罗斯套娃信封问题

力扣 354. 俄罗斯套娃信封问题

题目说明

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

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

不允许旋转信封。

示例

例1

1
2
3

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

笔者理解

此题是一道数组算法问题，在力扣题库中被定义为困难题。

解法

当笔者阅读完此题后，发现此题比较重要的是两点：大家想必都会想到要将数组排序，然后w升序依次排序，这样前一个信封就有可能被下一个信封装下，但是需要注意的是，题目中提到，”当另一个信封的宽度和高度都比这个信封大的时候”才能放进去，所以我们要将宽度相同的信封按h降序排列，然后我们就这样把这个问题变成一维问题了，只要比较h，最长的一个升序子序列就是套娃的最终答案，

例如：[[1,2],[1,1],[2,3],[2,2],[3,4],[3,2],[5,5]]（此时已经按w升序，h降序排列好了）

然后我们不难发现只要将{2，1，3，2，4，2，5}中的最长升序子序列求出来即可，即1，2，4，5，也就是信封中的[[1,1],[2,2],[3,4],[5,5]]，读者们可以自行验证一下，让我们来看看具体如何实现的吧。

实现

public int maxEnvelopes(int[][] envelopes) {
        if(envelopes.length==0) { return 0;}
        //空数组返回0

        int result = 0;
        int n = envelopes.length;
        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];
        //动态规划数组

        Arrays.fill(dp,1);
        //每个信封都至少包括自己这一个

        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < i; j++) {
                if(envelopes[i][0]>envelopes[j][0]&&envelopes[i][1]>envelopes[j][1]){
                    dp[i] = Math.max(dp[i],dp[j]+1);
                    //如果当前i信封能放进j信封，就取i信封的最大套娃数和j信封的最大套娃数+1中的较大值
                }
            }
            result = Math.max(result,dp[i]);
            //每计算出一个信封的最大套娃数就比较存储一次最大值
        }
        return result;
    }