LeetCode 646. Maximum Length of

@(LeetCode)

问题描述

给定 n 对数。在每对数中，第一个数始终小于第二个数。

我们定义：当 b < c 时， 数字对 (c, d) 可以跟在 (a, b) 后面。以这种格式形成链式的数字对。

给定一个数字对集合，找出最长的链式数字对。你不需要用完所有的数字对，可以任意选择数字对的顺序。

栗 1：

输入: [[1,2], [2,3], [3,4]]
输出: 2
解释: 最长的链式数字对为： [1,2] -> [3,4]

想看英文原文的戳这里。

解题思路

这道题比较简单，下面直接说下思路。

由于第一个数字始终是小于第二个数字，如果要找出最长的链式数字对，很容易推断出第二个数字肯定是越小越好，因为它能连接更多的数字对。

那么只需按照第二个数字从小到大进行排序，再从头逐一比较，判断当前数字对的最小值是否大于前一个数字对的最大值即可。

判断条件的代码表示如下：

// preMax 表示前一个数字对的最大值，pair 表示当前数字对。
pair[i][0] > preMax

完整代码：

var findLongestChain = function (pairs) {
  if (pairs && pairs.length > 0) {
    // 按 pair[1] 从小到大排序
    const sortedParis = pairs.sort((a, b) => {
      if (a[1] < b[1]) {
        return -1
      } else if (a[1] > b[1]) {
        return 1
      }

      return 0
    })

    let count = 1
    let preMax = sortedParis[0][1]
    let i = 1
    while (i < sortedParis.length) {
      const pair = sortedParis[i]
      if (pair[0] > preMax) {
        count += 1
        preMax = pair[1]
      }

      i += 1
    }

    return count
  }

  return 0
};