何为最长递增子序列

在计算机科学中，最长递增子序列（longest increasing subsequence）问题是指，在一个给定的数值序列中，找到一个子序列，使得这个子序列元素的数值依次递增，并且这个子序列的长度尽可能地大。最长递增子序列中的元素在原序列中不一定是连续的--[维基百科]( 最长递增子序列 - 维基百科，自由的百科全书 (wikipedia.org) )

求解最长递增子序列的长度

对于给定的原始序列的最长递增子序列可能有多解，那Vue3的快速Diff算法中求解的最长递增子序列，是求解出所有的子序列，还是基于某种算法的一种解呢？值得注意的是，虽然满足条件的子序列可能有多种，但其长度确是相同的。即，最长递增子序列的长度的求解具有唯一性。所以我们先来解LeetCode上的一道算法题。

300.最长递增子序列

测试用例及思路讨论

求解使用的用例：[10, 9, 2, 5, 3, 7, 21, 18]

思路分析：如，维护一个空数组，遍历原数组，先放入10，然后，9小于10，不放入。。。依次判断。。。【误区！】

解法一：动态规划(O(N^2))

Copilot给出的解法。

* @param nums * @returns number * 复杂度分析 * 时间复杂度：O(n^2) * 其中 n 为数组 nums 的长度，动态规划的状态数为 n，计算状态 dp [i] 时，需要 O(n) 的时间遍历 dp [0…i−1] 的所有状态 * 空间复杂度：O(n) * 需要额外使用长度为 n 的 dp 数组 function lengthOfLIS(nums: number [] ): number { if ( nums.length === 0 ) return 0 // 动态规划，从大变小，每个元素都至少可以单独成为子序列，此时长度都为 1 // 声明数组dp，dp [i] 的值代表 nums [i] 结尾的最长子序列长度 let dp: number [] = new Array(nums.length).fill(1) for (let i = 1 ; i < nums.length; i++) { for (let j = 0 ; j < i; j++) { // 如果nums [i] 大于nums [j] ，nums [i] 可以接在 nums [j] 之后（因为要求严格递增【排除了相等等情况】），此情况下最长子序列长度为 dp [j] + 1 if (nums [j] < nums [i] ) { dp [i] = Math.max(dp [i] , dp [j] + 1) return Math.max(...dp)

打断点分析

* @Description: 贪心算法（尽可能小的值的一个一个放入）+二分查找 * 分析可优化方案（O(N^2)数据大时，低性能很明显）： * 动态规划中，通过线性遍历来计算 dp 的复杂度无法降低 * 如果，我们要使子序列尽可能的长，则需要让序列递增得尽可能慢，因此我们希望每次在上升子序列最后加上的那个数尽可能的小，同时要做到比较的过程复杂度低于O(N) * 故需要维护，不同长度时的子序列的最后元素（其目的用于比较）构成的数组，遍历原数组（O(N)）使用二分查找(O(logN))来找到最合适的位置进行替换---保证子序列尽可能慢的递增 * @Author: ljy * @Date: 2022-05-03 12:43:19 * @LastEditors: ljy * @LastEditTime: 2022-05-09 01:51:24 * @FilePath: \longest-increasing-subsequence\lengthByDichotomy.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++ 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) { const mid = (left + right) >> 1 if (tails [mid] < nums [i] ) { left = mid + 1 } else { right = mid tails [left] = nums [i] // 打印tails数组---不能等同于不同长度时对应的子序列，因为遇到小的数，会插在更前面，改变了在元素组的位置（证明用例 [10, 9, 2, 5, 3, 7, 1, 18] 中的1插入时） // console.log(tails) return result

打断点分析

Vue3快速Diff算法中的实现

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

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]插入时，递增序列前一个元素的真实值。
Vue3的快速Diff算法中，利用贪心算法求解最长递增子序列，而不是求解所有的可能。出道算法题：给一个整数的数组，求解其所有可能的最长递增子序列。参考LeetCode 673
PS：推荐一个VScode插件--Vscode Google Translate，查看框架源码等api时自动翻译注释。
  分类：
 前端
 标签：
 源码