最长递增子序列

题目描述

给你一个整数数组 nums ，找到其中最长严格递增子序列。

输入：nums = [10,9,2,5,3,7,101,18]

输出：[2,3,7,101]

输入：nums = [0,1,0,3,2,3]

输出：[0,1,2,3]

算法思路

使用动态规划求解，vue中使用了贪心算法和二分查找来优化时间复杂度。真的难:( 以下写个简单的

思路:

每次遍历都更新当前行的最后一个元素，若当前元素大于当前行的最后一个元素，则可以接上，若不能接上，则替换第一行的元素。

代码实现

/**
 * @param {number[]} nums
 * @return {number}
 */
function lengthOfLIS(nums) {
  const len = nums.length
  if (len < 1)
    return
  const result = [[nums[0]]]

  for (let i = 1; i < len; i++) {
    // 更新方法
    _update(nums[i])
  }
  function _update(n) {
    // 倒叙遍历dp数组
    for (let i = result.length - 1; i >= 0; i--) {
      const curLine = result[i] // 当前行
      const last = curLine[curLine.length - 1]
      if (n > last) { // 说明可以接上 在下一行接上
        result[i + 1] = [...curLine, n]
        return
      }
    }
    // 如果一个都接不上
    // 替换第一行
    result[0] = [n]
  }
  return result[result.length - 1]
}