[354] 俄罗斯套娃信封问题

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

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

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

注意：不允许旋转信封。

示例 1：

输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]

输出：3

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

示例 2：

输入：envelopes = [[1,1],[1,1],[1,1]]

输出：1

提示：

1 <= envelopes.length <= 10^5

envelopes[i].length == 2

1 <= wi, hi <= 10^5

这道题很有意思，让我们通过套娃的方式塞入信封，求怎样塞可以塞得数量最多。

由于对于每一个信封，仅有取与不取两种情况，我们首先想到的就是 0-1 背包问题，但这里背包的判断维度是一个二维，因此我们需要将信封进行一次排序，先保证有一个维度（宽或高）的顺序是有序的，锁住一个维度，这样一来就变成了一个正常的 0-1 背包问题了。

递归写法如下：

function maxEnvelopes(envelopes: number[][]): number {
  const len = envelopes.length;
  // 先把 width 从大到小排序，先保证一个维度的顺序嵌套
  envelopes.sort((a, b) => a[0] === b[0] ? b[1] - a[1] : b[0] - a[0]);
  const res = dfs(0, Number.MAX_SAFE_INTEGER, Number.MAX_SAFE_INTEGER, 0);
  return res;

  function dfs(index: number, maxWidth: number, maxHeight: number, count: number): number {
    if (index >= len) return count;
    const [width, height] = envelopes[index];
    if (width < maxWidth && height < maxHeight) {
      return Math.max(dfs(index + 1, width, height, count + 1), dfs(index + 1, maxWidth, maxHeight, count));
    } else {
      return dfs(index + 1, maxWidth, maxHeight, count);
    }
  }
}

但这样写是会 TLE 的，因此这里需要对运算效率进行优化。

有了先固定一个维度的想法，那么剩下的一个维度，是不是选取方式只要符合单调递增，就能得到嵌套最大值了呢？实际上，这就将题目转化为了一个求最长递增子序列的问题。

题目中说了，长或宽相等时也不能进行嵌套。那么怎么解决呢？其实我们可以在排序上动手脚。排序时，先按宽度从小到大排序，宽度相等时，按高度从大到小排序。这样最长子序列中的高度元素在宽度相等时一定选取的是最大的那个，从而规避了这个问题。

function maxEnvelopes(envelopes: number[][]): number {
  // 先把 width 从大到小排序，先保证一个维度的顺序嵌套
  envelopes.sort((a, b) => (a[0] === b[0] ? b[1] - a[1] : a[0] - b[0]));
  const heights = envelopes.map(x => x[1]);
  const res = lengthOfLIS(heights);
  return res;

  function lengthOfLIS(nums: number[]): number {
    const len = nums.length;
    const dp: number[] = Array(len).fill(1);
    for (let i = 0; i < len; i++) {
      for (let j = 0; j < i; j++) {
        if (nums[i] > nums[j]) {
          dp[i] = Math.max(dp[i], dp[j] + 1);
        }
      }
    }
    const max = dp.reduce((prev, curr) => Math.max(prev, curr));
    return max;
  }
}

但这样居然还是会 TLE！不愧是 hard 难度的题目。这里就需要对最长递增子序列算法进行优化了。

我们可以利用二分查找，遍历nums数组时，使用左边界二分法判断当前元素是否可以替换LIS中的元素，形成新的最小递增子序列。

当前元素比LIS中的所有元素都大时，说明递增序列的长度可以增加，此时将该元素push进入LIS。

最后返回该LIS的长度，即为nums最大子序列的长度了。注意，这里LIS中元素的顺序并不一定是真实的LIS，只是长度相等而已。

function maxEnvelopes(envelopes: number[][]): number {
  // 先把 width 从大到小排序，先保证一个维度的顺序嵌套
  envelopes.sort((a, b) => (a[0] === b[0] ? b[1] - a[1] : a[0] - b[0]));
  const heights = envelopes.map(x => x[1]);
  const res = lengthOfLIS(heights);
  return res;

  function lengthOfLIS(nums: number[]): number {
    // 维护一个最小递增子序列
    const lis: number[] = [];
    // Sn = (Sn-1, An)为递增子序列 ? Sn-1 + 1 : Sn-1
    for (let i = 0; i < nums.length; i++) {
      let left = 0;
      let right = lis.length - 1;
      // 求左边界的二分法
      while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (lis[mid] < nums[i]) {
          left = mid + 1;
        } else {
          right = mid - 1;
        }
      }
      if (left >= lis.length) {
        // 边界越界，说明此时子 LIS 中不存在比 nums[i] 大的数，LIS 数组增加一位
        lis.push(nums[i]);
      } else {
        // 否则更新该 LIS 位置上的数字
        lis[left] = nums[i];
      }
    }
    return lis.length;
  }
}