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

野性酷女 2023-09-23 15:41 82阅读 0赞

### 题目来源 ###

[354. 俄罗斯套娃信封问题 - 力扣（LeetCode）][354. _ - _LeetCode]

### 题目描述 ###

给你一个二维整数数组 envelopes ，其中 envelopes\[i\] = \[wi, hi\] ，表示第 i 个信封的宽度和高度。

当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。

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

注意：不允许旋转信封。

### 示例 ###

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td style="width:97px;">输入</td> 
   <td style="width:401px;">envelopes = [[5,4],[6,4],[6,7],[2,3]]</td> 
  </tr> 
  <tr> 
   <td style="width:97px;">输出</td> 
   <td style="width:401px;">3</td> 
  </tr> 
  <tr> 
   <td style="width:97px;">说明</td> 
   <td style="width:401px;">最多信封的个数为 3, 组合为: [2,3] =&gt; [5,4] =&gt; [6,7]。</td> 
  </tr> 
 </tbody> 
</table>

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td style="width:97px;">输入</td> 
   <td style="width:401px;">envelopes = [[1,1],[1,1],[1,1]]</td> 
  </tr> 
  <tr> 
   <td style="width:97px;">输出</td> 
   <td style="width:401px;">1</td> 
  </tr> 
  <tr> 
   <td style="width:97px;">说明</td> 
   <td style="width:401px;">无</td> 
  </tr> 
 </tbody> 
</table>

### 提示 ###

*  1 <= envelopes.length <= 105
 *  envelopes\[i\].length == 2
 *  1 <= wi, hi <= 105

### 题目解析 ###

本题要求信封套信封，且外部的信封的宽、高必须都大于内部的信封的宽、高，问最多能套几个。

首先，我们很容易想到，将所有信封按照宽度升序，这样就可以保证只看宽度的话，排序靠前的信封可以被排序靠后的信封套进去。

真的是这样吗？

如果有两个宽度相同的信封，那么它们就无法嵌套。

因此，我们需要排除掉宽度相同的情况。

一种方案是dfs，比如宽度有 \[1,2,3,3,4,5,5,5\]

则宽度上一共有：2\*3=6种嵌套方案，即不看宽度唯一的，那么只剩下\[3,3,5,5,5\]，而重复的宽度的高度可能不同，因此这里需要求包含重复情况组合。

但是这种方案非常麻烦，也浪费性能。

有一种更好的方案，那就是宽度重复的情况不用管，我们只需要将宽度相同的信封的高度从大到小排序即可。

原因是，信封嵌套，不经要求宽度内小外大，高度也要求内小外大，因此如果两个信封宽度相同，而它们的高度降序的话，则排序靠后的信封也无法套进前面的信封。

因此，我们首先需要将，信封按照宽度升序，对于宽度相同的信封，则按照高度降序。

那么宽度一维就搞定，接下来就是求高度一维的最长递增子序列了，而关于最长递增子序列的求解请看这个博客

[LeetCode - 300 最长递增子序列\_伏城之外的博客-CSDN博客][LeetCode - 300 _-CSDN]

这个博客种提供了三种方案：  
1、动态规划

2、耐心排序 + 顺序查找

3、耐心排序 + 二分查找

其中耐心排序 + 二分查找是时间复杂度最低的，为O(nlgn)

### 算法源码 ###

/**
     * @param {number[][]} envelopes
     * @return {number}
     */
    var maxEnvelopes = function (envelopes) {
      const heights = envelopes
        .sort((a, b) => (a[0] === b[0] ? b[1] - a[1] : a[0] - b[0]))
        .map((envelope) => envelope[1]);
    
      return getMaxLenLIS(heights);
    };
    
    function getMaxLenLIS(nums) {
      const dp = [nums[0]];
    
      for (let i = 1; i < nums.length; i++) {
        if (nums[i] > dp[dp.length - 1]) {
          dp.push(nums[i]);
          continue;
        }
    
        if (nums[i] < dp[0]) {
          dp[0] = nums[i];
          continue;
        }
    
        const idx = binarySearch(dp, nums[i]);
        if (idx < 0) dp[-idx - 1] = nums[i];
      }
    
      return dp.length;
    }
    
    function binarySearch(arr, key, from = 0, to = arr.length) {
      let high = to - 1;
      let low = from;
    
      while (low <= high) {
        let mid = (high + low) >>> 1;
        let midVal = arr[mid];
    
        if (key < midVal) {
          high = mid - 1;
        } else if (key > midVal) {
          low = mid + 1;
        } else {
          return mid;
        }
      }
      return -(low + 1);
    }

![f7ebf9288cd24966b8bb590453ec8db1.png][]

[354. _ - _LeetCode]: https://leetcode.cn/problems/russian-doll-envelopes/
[LeetCode - 300 _-CSDN]: https://blog.csdn.net/qfc_128220/article/details/127931755?spm=1001.2014.3001.5502
[f7ebf9288cd24966b8bb590453ec8db1.png]: https://img-blog.csdnimg.cn/f7ebf9288cd24966b8bb590453ec8db1.png