300. 最长递增子序列

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。
子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：
输入：nums = [0,1,0,3,2,3]
输出：4

示例 3：
输入：nums = [7,7,7,7,7,7,7]
输出：1

提示：
1 <= nums.length <= 2500
-104 <= nums[i] <= 104

进阶：你能将算法的时间复杂度降低到 O(n log(n)) 吗?

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/longest-increasing-subsequence

javascript

/**
 * @param {number[]} nums
 * @return {number}
*/
// var lengthOfLIS = function(nums) {
//   const len = nums.length
//   const res = Array.from({length: len}, () => 1)
//   for (let i = 1; i < len; i++) {
//     for (let j = 0; j < i; j++) {
//       if (nums[i] > nums[j]) {
//         res[i] = Math.max(res[i], res[j] + 1)
//       }
//     }
//   }

//   return Math.max(...res)
// };

// var lengthOfLIS = function(nums) {
//   const len = nums.length
//   const res = [nums[0]]
//   for (let i = 1; i < len; i++) {
//     const cur = nums[i]
//     if (nums[i] > res[res.length - 1]) {
//       res.push(cur)
//     } else {
//       let left = 0
//       let right = res.length - 1
//       while (left < right) {
//         const mid = Math.floor((left + right) / 2)
//         if (res[mid] < cur) {
//           left = mid + 1
//         } else {
//           right = mid
//         }
//       }
//       res[right] = cur
//     }
//   }
//   return res.length
// }

var lengthOfLIS = function(nums) {
  const len = nums.length
  const p = Array.from({length: len})
  const res = [0]
  let l, r
  for (let i = 1; i < len; i++) {
    const cur = nums[i], j = res[res.length - 1]
    if(nums[j] < cur) {
      p[i] = j
      res.push(i)
      continue
    }
    l = 0, r = res.length - 1
    while(l < r) {
      const mid = l + r >> 1
      if(nums[res[mid]] < cur) {
        l = mid + 1
      }else {
        r = mid
      }
    }
    if(nums[res[l]] > cur) {
      if(l > 0){
        p[i] = res[l - 1]
      }
      res[l] = i
    }
  }

  r = res.length - 1
  l = p[res[r]]

  while(r--){
    res[r] = l
    l = p[l]
  }

  return res
}
// console.log(lengthOfLIS([6,7,1,2,3]))
// console.log(lengthOfLIS([2,1,5,3,6,4,8,9,7]))
// console.log(lengthOfLIS([10,9,2,5,3,7,101,18]))
// console.log(lengthOfLIS([0,1,0,3,2,3]))
// console.log(lengthOfLIS([7,7,7,7,7,7,7]))

300. 最长递增子序列 #

300. 最长递增子序列