题目描述

给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。
当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
注意：不允许旋转信封。

示例1：

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

思路

1、刚开始想用4个变量 max_w，max_h，min_w，min_h 去遍历所有的信封，然后发现只用这4个变量不足以应付所有情况（比如当前信封的 w 和 h 处于最大值和最小值之间，无法处理）。
2、因为信封的 w 和 h 均在变化，所以先固定一维，再进行讨论。

解法一

  • 核心思想：通过固定 w（对 w 进行升序排序），当 w 相同时，对 h 进行降序排序，然后在 h 这一维上求解最长递增子序列长度，即为该题目的答案。（将题目转化为一维的LIS问题）。

  • 补充说明：为什么要对 h 进行降序排序。考虑一种情况，当envelopes = [[1,1],[1,2],[1,3],[1,4]]时，由于我们忽略了 w 维度，只对 h 维度进行LIS问题求解（因为我们默认 w 在排完序后是单调递增的，未处理 w 相同时的情况）。这样求解出来的答案是4。并不符合题目的设定。

    因此，我们必须要保证对于每一种 w 值，我们最多只能选择 11个信封。 我们可以将 h 值作为排序的第二关键字进行降序排序，这样一来，对于每一种 w 值，其对应的信封在排序后的数组中是按照 h 值递减的顺序出现的，那么这些 hh值不可能组成长度超过 1 的严格递增的序列，这就从根本上杜绝了错误的出现。

  • 时间复杂度：O(N2)。

  • 空间复杂度：O(N)

  • 代码

    1. class Solution {
    2.   public int maxEnvelopes(int[][] envelopes) {
    3.       if(envelopes.length == 0){
    4.           return 0;
    5.       }
    7.       int n = envelopes.length;
    8.       Arrays.sort(envelopes, new Comparator<int[]>(){
    9.           public int compare(int[] e1, int[] e2){
    10.               if(e1[0] != e2[0]){
    11.                   return e1[0] - e2[0];
    12.               }else{
    13.                   return e2[1] - e1[1];
    14.               }
    15.           }
    16.       });
    18.       int[] f = new int[n];
    19.       Arrays.fill(f,1);
    20.       int ans = 1;
    21.       for(int i = 1; i < n; i++){
    22.           for(int j = 0; j < i; j++){
    23.               if(envelopes[j][1] < envelopes[i][1]){
    24.                   f[i] = Math.max(f[i], f[j]+1);
    25.               }
    26.           }
    27.           ans = Math.max(f[i], ans);
    28.       }
    29.       return ans;
    30.   }
    31. }

解法二

  • 核心思想：同样需要对原数据在第1维上升序排序，当第1维数据相同时对第2维的数据进行降序排序。但是，在此不再维护一个 LIS 问题的 dp[]，而是维护一个单调递增序列。
  • 状态定义：dp[i] 为 长度为 i + 1 的最长递增子序列，且该序列的末尾元素为 nums[i]。
  • 解释说明：例如 dp={1,3,6}，代表长度为1的最长递增子序列的末尾元素为1，代表长度为2的最长递增子序列的末尾元素为3，代表长度为3的最长递增子序列的末尾元素为6。

  • 问题求解

    1、在排完序后，将 h 单独拿出来，形成一个新的数组 h[]。 2、初始化 dp（用 ArrayList 初始化，并将 h[0] 加入 list 中）。 3、遍历 [1,n) 区间（h 数组），对于每一个值 x，判断 x 在 dp[] 中的位置，做以下判断： 1、当 dp 中仅存在某值满足 y > x：使用 x 替换该值 y。
    2、当 dp 中存在多值满足 yt > y2 > y1 > x，使用 x 替换符合条件的最小值 y1。（因为 dp[] 是单调递增的，所以遇到的第一个符合条件的 y 一定是所有符合条件的 y 里面最小的，直接返回即可，不用再循环下去） 3、当 dp 中不存在值满足 y > x：将 x 添加到 dp 数组最末端。 4、dp[] 的长度即为问题的解。

  • 时间复杂度：O(N∗len(dp))。这个方法较解法一已经有了进一步的优化，但是假如一开始给定的就是一个层层套娃的合法序列，那么最差时间复杂度仍然能达到O(N2)。

  • 空间复杂度：O(N)。

  • 代码

    1. class Solution {
    2.   public int maxEnvelopes(int[][] envelopes) {
    3.       if(envelopes.length == 0){
    4.           return 0;
    5.       }
    7.       int n = envelopes.length;
    8.       Arrays.sort(envelopes, new Comparator<int[]>(){
    9.           public int compare(int[] e1, int[] e2){
    10.               if(e1[0] != e2[0]){
    11.                   return e1[0] - e2[0];
    12.               }else{
    13.                   return e2[1] - e1[1];
    14.               }
    15.           }
    16.       });
    18.       List<Integer> dp = new ArrayList<Integer>();
    19.       dp.add(envelopes[0][1]);
    20.       for(int i = 1; i < n; i++){
    21.           int j = 0;
    22.           for(; j < dp.size(); j++){
    23.               if(dp.get(j) >= envelopes[i][1]){
    24.                   dp.set(j, envelopes[i][1]);
    25.                   break;
    26.               } 
    27.           }
    28.           if(j == dp.size())
    29.               dp.add(envelopes[i][1]);
    30.       }
    31.       return dp.size();
    32.   }
    33. }