周星星

Appearance

题目 ​

给你一个整数数组 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 。
输入：nums = [10,9,2,5,3,7,101,18]
输出：4
解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。

示例 2：

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

示例 3：

输入：nums = [7,7,7,7,7,7,7]
输出：1
输入：nums = [7,7,7,7,7,7,7]
输出：1

提示：

  • 1 <= nums.length <= 2500
  • -104 <= nums[i] <= 104

进阶：

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

理解题目 ​

给定一个数组，从数组中寻找递增组成的新数组的长度

题解 ​

利用当前项去跟当前的前一项去比较，如果 nums[i]>nums[i-1]那么就是递增的 动态规划，从大变小，每个元素都至少可以单独成为子序列，此时长度都为 1 声明数组 dp，dp[i]的值代表 nums[i] 结尾的最长子序列长度：即递增的长度 当我们去比较的是，前面一项之前已经比较过了她也存了之前递增的长度了，依次向前拿去即可 当拿到的前一项的长度+1 和当前项的长度取最大值 赋值给当前项的长度

答案 ​

动态规划

ts
function lengthOfLIS(nums: number[]): number {
  if (nums.length === 0) return 0;
  // 动态规划，从大变小，每个元素都至少可以单独成为子序列，此时长度都为 1
  // 声明数组dp，dp[i]的值代表 nums[i] 结尾的最长子序列长度
  let dp = new Array(nums.length).fill(1);
  for (let i = 1; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      // num[i]:当前项，nums[j]当前项的前一项
      // 如果nums[i]大于nums[j]，nums[i] 可以接在 nums[j] 之后（因为要求严格递增【排除了相等等情况】），
      // 此情况下最长子序列长度为 dp[j] + 1
      // console.log(i,j)
      if (nums[i] > nums[j]) {
        // console.log([10, 9, 2, 5, 3, 7, 21, 18], dp);
        // console.log(`i=${i},nums[${i}]=${nums[i]},j=${j},nums[${j}]=${nums[j]},dp[${i}]=${dp[i]},dp[${j}]=${dp[j]},dp[${j}] + 1=${dp[j] + 1}`);
        // console.log(`因为Math.max(dp[${i}], dp[${j}] + 1)所以dp[${i}]=${Math.max(dp[i], dp[j] + 1)}`);
        // debugger
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
      // console.log("=========");
    }
  }
  // console.log(dp)
  return Math.max(...dp);
}
function lengthOfLIS(nums: number[]): number {
  if (nums.length === 0) return 0;
  // 动态规划，从大变小，每个元素都至少可以单独成为子序列，此时长度都为 1
  // 声明数组dp，dp[i]的值代表 nums[i] 结尾的最长子序列长度
  let dp = new Array(nums.length).fill(1);
  for (let i = 1; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      // num[i]:当前项，nums[j]当前项的前一项
      // 如果nums[i]大于nums[j]，nums[i] 可以接在 nums[j] 之后（因为要求严格递增【排除了相等等情况】），
      // 此情况下最长子序列长度为 dp[j] + 1
      // console.log(i,j)
      if (nums[i] > nums[j]) {
        // console.log([10, 9, 2, 5, 3, 7, 21, 18], dp);
        // console.log(`i=${i},nums[${i}]=${nums[i]},j=${j},nums[${j}]=${nums[j]},dp[${i}]=${dp[i]},dp[${j}]=${dp[j]},dp[${j}] + 1=${dp[j] + 1}`);
        // console.log(`因为Math.max(dp[${i}], dp[${j}] + 1)所以dp[${i}]=${Math.max(dp[i], dp[j] + 1)}`);
        // debugger
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
      // console.log("=========");
    }
  }
  // console.log(dp)
  return Math.max(...dp);
}

二分搜索法+位运算+贪心算法

ts

/**
 * 
 * @param nums 
 * @returns 
 * 复杂度分析
 * 时间复杂度：O(nlogn)
 * 遍历 nums 列表需 O(N)，在每个 nums[i] 二分法需 O(logN)
 * 空间复杂度：O(n)
 * tails需要额外空间
 */
 function lengthByDichotomy(nums: number[]): number {
    if (nums.length === 0) return 0
    // 维护一个数组 tails，其中每个元素 tails[k] 的值代表 长度为 k+1 的子序列尾部元素的值（k为自然数）
    // 如tail[0]是求长度为1的连续子序列时的最小末尾元素
    // 例：在 1 8 4中 tail[0]=1 tail[1]=4 没有tail[2] 因为无法到达长度为3的连续子序列
    // 初始tails数组[0],其值为子序列列长度为1，即num[0]
    // 由于js数组的特点，可以不用初始化tails数组的长度，不用每个元素都初始化0---当然初始化也是可以的
    let tails: number[] = [nums[0]]    
    // 设 result 为 tails 当前长度，代表直到当前的最长递增子序列长度
    let result = 1
    // 从nums第二个元素开始遍历数组
    for (let i = 1; i < nums.length; i++) {
        // 比 tails[result] 大，则更新 tails[result]，同时 result++
        // console.log(i,result,nums[i] > tails[result-1])
        if (nums[i] > tails[result-1]) {
            tails[++result - 1] = nums[i]
        } else {
            // 否则，使用二分查找法，找到比 nums[i] 大的最小的 tails[j]，即tails[j]<nums[i]<tails[j+1]，然后更新 tails[j]
            let left = 0, right = result
            while (left < right) {
                // 这里运用了位运算,为什么可以这么算呢?
                // >>相当于处于2
                //那这里为什么除以2呢？
                //根据二分搜索法 基本原理：
                /**
                 * 首先将要查找的元素[key]与数组的中间元素比较
                 * 1、如果key元素小于中间元素，组需要在数组的前一半中继续查找
                 * 2、如果key和中间元素相等，匹配成功，查找结束
                 * 3、如果key大于中间元素，只需要在数组的后一般元素中继续查找key
                 */
                const mid = (left + right) >> 1
                // console.log("if (tails[mid] < nums[i]) {",tails[mid],nums[i])
                if (tails[mid] < nums[i]) {
                    left = mid + 1
                } else {
                    right = mid
                }
            }
            tails[left] = nums[i]
            // console.log('tails[left] = nums[i]',tails[left])
        }
        // 打印tails数组---不能等同于不同长度时对应的子序列，因为遇到小的数，会插在更前面，改变了在元素组的位置（证明用例[10, 9, 2, 5, 3, 7, 1, 18]中的1插入时）
        // console.log(tails)
    }
    return result
}

/**
 * 
 * @param nums 
 * @returns 
 * 复杂度分析
 * 时间复杂度：O(nlogn)
 * 遍历 nums 列表需 O(N)，在每个 nums[i] 二分法需 O(logN)
 * 空间复杂度：O(n)
 * tails需要额外空间
 */
 function lengthByDichotomy(nums: number[]): number {
    if (nums.length === 0) return 0
    // 维护一个数组 tails，其中每个元素 tails[k] 的值代表 长度为 k+1 的子序列尾部元素的值（k为自然数）
    // 如tail[0]是求长度为1的连续子序列时的最小末尾元素
    // 例：在 1 8 4中 tail[0]=1 tail[1]=4 没有tail[2] 因为无法到达长度为3的连续子序列
    // 初始tails数组[0],其值为子序列列长度为1，即num[0]
    // 由于js数组的特点，可以不用初始化tails数组的长度，不用每个元素都初始化0---当然初始化也是可以的
    let tails: number[] = [nums[0]]    
    // 设 result 为 tails 当前长度，代表直到当前的最长递增子序列长度
    let result = 1
    // 从nums第二个元素开始遍历数组
    for (let i = 1; i < nums.length; i++) {
        // 比 tails[result] 大，则更新 tails[result]，同时 result++
        // console.log(i,result,nums[i] > tails[result-1])
        if (nums[i] > tails[result-1]) {
            tails[++result - 1] = nums[i]
        } else {
            // 否则，使用二分查找法，找到比 nums[i] 大的最小的 tails[j]，即tails[j]<nums[i]<tails[j+1]，然后更新 tails[j]
            let left = 0, right = result
            while (left < right) {
                // 这里运用了位运算,为什么可以这么算呢?
                // >>相当于处于2
                //那这里为什么除以2呢？
                //根据二分搜索法 基本原理：
                /**
                 * 首先将要查找的元素[key]与数组的中间元素比较
                 * 1、如果key元素小于中间元素，组需要在数组的前一半中继续查找
                 * 2、如果key和中间元素相等，匹配成功，查找结束
                 * 3、如果key大于中间元素，只需要在数组的后一般元素中继续查找key
                 */
                const mid = (left + right) >> 1
                // console.log("if (tails[mid] < nums[i]) {",tails[mid],nums[i])
                if (tails[mid] < nums[i]) {
                    left = mid + 1
                } else {
                    right = mid
                }
            }
            tails[left] = nums[i]
            // console.log('tails[left] = nums[i]',tails[left])
        }
        // 打印tails数组---不能等同于不同长度时对应的子序列，因为遇到小的数，会插在更前面，改变了在元素组的位置（证明用例[10, 9, 2, 5, 3, 7, 1, 18]中的1插入时）
        // console.log(tails)
    }
    return result
}

Vue3快速Diff算法中的实现 ​

注意：在快速Diff算法中，求解最长递增子序列的目的是对子节点重新编号，所以肯定不只是求解出长度即可。

ts
function getSequence(arr: number[]): number[] {
    const p = arr.slice()
    const result = [0]
    let i, j, u, v, c
    const len = arr.length
    for (i = 0; i < len; i++) {
        const arrI = arr[i]
        if (arrI !== 0) {
            j = result[result.length - 1]
            if (arr[j] < arrI) {
                p[i] = j
                result.push(i)
                continue
            }
            u = 0
            v = result.length - 1
            while (u < v) {
                c = (u + v) >> 1
                if (arr[result[c]] < arrI) {
                    u = c + 1
                } else {
                    v = c
                }
            }
            if (arrI < arr[result[u]]) {
                if (u > 0) {
                    p[i] = result[u - 1]
                }
                result[u] = i
            }
        }
    }
    u = result.length
    v = result[u - 1]
    while (u-- > 0) {
        result[u] = v
        v = p[v]
    }
    return result
}
function getSequence(arr: number[]): number[] {
    const p = arr.slice()
    const result = [0]
    let i, j, u, v, c
    const len = arr.length
    for (i = 0; i < len; i++) {
        const arrI = arr[i]
        if (arrI !== 0) {
            j = result[result.length - 1]
            if (arr[j] < arrI) {
                p[i] = j
                result.push(i)
                continue
            }
            u = 0
            v = result.length - 1
            while (u < v) {
                c = (u + v) >> 1
                if (arr[result[c]] < arrI) {
                    u = c + 1
                } else {
                    v = c
                }
            }
            if (arrI < arr[result[u]]) {
                if (u > 0) {
                    p[i] = result[u - 1]
                }
                result[u] = i
            }
        }
    }
    u = result.length
    v = result[u - 1]
    while (u-- > 0) {
        result[u] = v
        v = p[v]
    }
    return result
}

分析：getSequence相比于解法二，思路相近。但除了求解出长度，还会回溯查找原数组的索引--通过维护数组p，p记录了当前位置元素arr[i]插入时，递增序列前一个元素的真实值。