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

题目来源

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

题目描述

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

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

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

注意：不允许旋转信封。

示例

提示

• 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博客

这个博客种提供了三种方案：
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);
}