354. 俄罗斯套娃信封问题（动态规划）

谁借莪１个温暖的怀抱￠ 2023-10-05 18:23 30阅读 0赞

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

*  题目
 *  解题思路
 *  代码

## 题目 ##

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

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

![在这里插入图片描述][20210125192140798.png]

**说明:**

*  **不允许旋转信封。**

## 解题思路 ##

因为我们写过一维的LIS算法。所以我们想办法往一维数组上面靠。  
我们把宽度W进行升序排序，然后遇到W相同的情况就按照高度H进行降序排序。最后把排序后的H作为一个一维数组，那么就可以用标准的LIS算法去解决这个一维数组。得到的结果就是我们要的结果。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70]  
**关键在于,对于宽度w相同的数对,要对其高度h进行降序排序。**  
因为两个W相同的信封不能相互包含,W相同时将h逆序排序,则这些逆序h中最  
多**只会有一个**被选入递增子序列,保证了最终的信封序列中不会出现w相同的情况。

## 代码 ##

class Solution {
        
    
        public int maxEnvelopes(int[][] envelopes) {
        
    
            int N = envelopes.length;
            if (N == 0) {
        
                return 0;
            }
    
            Arrays.sort(envelopes, new Comparator<int[]>() {
        
                //按照每个信封的宽度进行升序排列，若宽度一样，则按高度降序排列
                public int compare(int[] a, int[] b) {
        
                    /*
                        a[0]、b[0]分别代表前一个、后一个数组的宽度
                        a[1]、b[1]分别代表前一个、后一个数组的宽度
                    */
                    return a[0] == b[0] ? b[1] - a[1] : a[0] - b[0];
                }
            });
                int[] target=new int[N];
    
                for(int i=0;i<N;i++){
        
                    target[i]=envelopes[i][1];//把排序后的高度单独提取出来
                }
    
            return lengthOfLIS(target);
    
        }
    
    
        //用来求最长递增子序列。这里稍微修改一下作为辅助方法
        public int lengthOfLIS(int[] nums) {
        
    
            if (nums.length == 0) {
        
                return 0;
            }
            int N = nums.length;
            //dp[i]存放的是：以nums[i]结尾的最长递增子序列的长度
            int[] dp = new int[N];
    
    
            //base case：将dp[]都初始化为1
            Arrays.fill(dp, 1);
    
            for (int i = 0; i < N; i++) {
        //i=N-1就是dp[]的最后一个元素了，原为dp[]的长度和nums[]的相同
                for (int j = 0; j < i; j++) {
        
                    if (nums[j] < nums[i]) {
        
                        dp[i] = Math.max(dp[i], dp[j] + 1);
                    }
                }
            }
    
            int res = 0;
            //来遍历一次经过整理的dp[]，找出最大值
            for (int i = 0; i < dp.length; i++) {
        
                res = Math.max(res, dp[i]);
            }
    
            return res;
    
        }
        
    }

[20210125192140798.png]: https://img-blog.csdnimg.cn/20210125192140798.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20210125192704989.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzIxMDQwNTU5,size_16,color_FFFFFF,t_70