🥇Hard

给定一些标记了宽度和高度的信封，宽度和高度以整数对形式 (w, h) 出现。当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。

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

说明:
不允许旋转信封。

示例1:

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

示例2:

  1. 输入:[ [ 1, 1 ], [ 2, 3 ], [ 4, 5 ], [ 4, 6 ], [ 6, 7 ] ]
  2. 输出：4

示例3:

  1. 输入:[[2,100],[3,200],[4,300],[5,500],[5,400],[5,250],[6,370],[6,360],[7,380]]
  2. 输出：5

题解

个人解法

想法是先按信封宽度从小到大排序，然后再一个一个比较高度就行。代码如下：

  1. /**
  2.  * @param {number[][]} envelopes
  3.  * @return {number}
  4.  */
  5. var maxEnvelopes = function(envelopes) {
  6.     if (envelopes.length === 0) return 0
  7.     envelopes.sort((a,b)=>a[0]-b[0])
  8.     let before = envelopes[0]
  9.     let count=1
  10.     for(let i=1;i<envelopes.length;i++){
  11.         if (envelopes[i][1]> before[1] && envelopes[i][0]> before[0]){
  12.             count++
  13.             before = envelopes[i]
  14.         }
  15.     }
  16.     return count
  18. };

但这样考虑还是不周到，例如示例3：[[2,100],[3,200],[4,300],[5,500],[5,400],[5,250],[6,370],[6,360],[7,380]]，排序之后，就是：

[[ 2, 100 ], [ 3, 200 ],[ 4, 300 ], [ 5, 500 ],[ 5, 400 ], [ 5, 250 ],[ 6, 370 ], [ 6, 360 ],[ 7, 380 ]]

按上面的逻辑，能套用的应该有[2,100],[3,200],[4,300],[5,500]，一共四个。而实际上套用的应该是[2,100],[3,200],[4,300],[6,370],[7,380]，一共五个。并不能简单的线性处理！