力扣挑战赛第8天-No.354俄罗斯套娃信封问题

题目描述

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

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

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

不允许旋转信封。

示例：

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

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

注意：

1 <= envelopes.length <= 5000
envelopes[i].length == 2
1 <= wi, hi <= 10^4

解法一

动态规划

/**
 * @param {number[][]} envelopes
 * @return {number}
 */
let maxEnvelopes = function (envelopes) {
  let n = envelopes.length;
  if (n === 0) {
    return 0;
  }
  /* w作为第一关键字升序排列，h作为第二关键字降序排列 */
  envelopes.sort((e1, e2) => {
    if (e1[0] !== e2[0]) {
      return e1[0] - e2[0];
    } else {
      return e2[1] - e1[1];
    }
  });
  /* dp[i]表示h的前i个元素可以组成的最长递增子序列的长度，且必须选择第i个元素 */
  let dp = new Array(n).fill(1);
  let ret = 1;
  for (let i = 1; i < n; i++) {
    for (let j = 0; j < i; j++) {
      if (envelopes[j][1] < envelopes[i][1]) {
        dp[i] = Math.max(dp[i], dp[j] + 1); // 状态转移
      }
    }
    ret = Math.max(ret, dp[i]);
  }
  return ret;
};

解法二

动态规划 + 二分查找

/**
 * @param {number[][]} envelopes
 * @return {number}
 */
let maxEnvelopes = function (envelopes) {
  let binarySearch = function (arr, target) {
    let low = 0;
    let high = arr.length - 1;
    while (low < high) {
      let mid = Math.floor((high - low) / 2) + low;
      if (arr[mid] < target) {
        low = mid + 1;
      } else {
        high = mid;
      }
    }
    return low;
  }
  let n = envelopes.length;
  if (n === 0) {
    return 0;
  }
  /* w作为第一关键字升序排列，h作为第二关键字降序排列 */
  envelopes.sort((e1, e2) => {
    if (e1[0] !== e2[0]) {
      return e1[0] - e2[0];
    } else {
      return e2[1] - e1[1];
    }
  });
  /* dp数组存放着最长递归子序列 */
  let dp = [envelopes[0][1]];
  for (let i = 1; i < n; i++) {
    let e = envelopes[i][1];
    if (e > dp[dp.length - 1]) {
      dp.push(e);
    } else {
      let index = binarySearch(dp, e);
      dp[index] = e;
    }
  }
  return dp.length;
};

Donate