300. 最长递增子序列

[Geekhyt]

原题链接

什么是上升子序列？

首先，我们需要对基本的概念进行了解和区分：

• 子串：一定是连续的
• 子序列：子序列不要求连续 例如：[6, 9, 12] 是 [1, 3, 6, 8, 9, 10, 12] 的一个子序列
• 上升/递增子序列：一定是严格上升/递增的子序列

注意：子序列中元素的相对顺序必须保持在原始数组中的相对顺序

题解

动态规划

关于动态规划的思想，还不了解的同学们可以移步我的这篇专栏入个门，「算法思想」分治、动态规划、回溯、贪心一锅炖

我们可以将状态 dp[i] 定义为以 nums[i] 这个数结尾(一定包括 nums[i])的最长递增子序列的长度，并将 dp[i] 初始化为 1，因为每个元素都是一个单独的子序列。

定义状态转移方程：

• 当我们遍历 nums[i] 时，需要同时对比已经遍历过的 nums[j]
• 如果 nums[i] > nums[j]，nums[i] 就可以加入到序列 nums[j] 的最后，长度就是 dp[j] + 1
  注：(0 <= j < i) (nums[j] < nums[i])

const lengthOfLIS = function(nums) {
    let n = nums.length
    if (n == 0) {
        return 0
    }
    let dp = new Array(n).fill(1)
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[j] < nums[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1)
            }
        }
    }
    return Math.max(...dp) 
}

• 时间复杂度：O(n^2)
• 空间复杂度：O(n)

这里我画了一张图，便于你理解。

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

贪心 + 二分查找

关于贪心和二分查找还不了解的同学们可以移步我的这两篇专栏入个门。

• 「算法思想」分治、动态规划、回溯、贪心一锅炖
• 从酒桌游戏看二分查找算法

这里再结合本题理解一下贪心思想，同样是长度为 2 的序列，[1,2] 一定比 [1,4] 好，因为它更有潜力。换句话说，我们想要组成最长的递增子序列，就要让这个子序列中上升的尽可能的慢，这样才能更长。

我们可以创建一个 tails 数组，用来保存最长递增子序列，如果当前遍历的 nums[i] 大于 tails 的最后一个元素(也就是 tails 中的最大值)时，我们将其追加到后面即可。否则的话，我们就查找 tails 中第一个大于 nums[i] 的数并替换它。因为是单调递增的序列，我们可以使用二分查找，将时间复杂度降低到 O(logn) 。

const lengthOfLIS = function(nums) {
    let len = nums.length
    if (len <= 1) {
        return len
    }
    let tails = [nums[0]]
    for (let i = 0; i < len; i++) {
        // 当前遍历元素 nums[i] 大于 前一个递增子序列的 尾元素时，追加到后面即可
        if (nums[i] > tails[tails.length - 1]) {
            tails.push(nums[i])
        } else {
            // 否则，查找递增子序列中第一个大于当前值的元素，用当前遍历元素 nums[i] 替换它
            // 递增序列，可以使用二分查找
            let left = 0
            let right = tails.length - 1
            while (left < right) {
                let mid = (left + right) >> 1;
                if (tails[mid] < nums[i]) {
                    left = mid + 1
                } else {
                    right = mid
                }
            }
            tails[left] = nums[i]
        }
    }
    return tails.length
}

• 时间复杂度：O(nlogn)
• 空间复杂度：O(n)

这里我画了一张图，便于你理解。

注意：这种方式被替换后组成的新数组不一定是解法一中正确结果的数组，但长度是一样的，不影响我们对此题求解。

比如这种情况：[1,4,5,2,3,7,0]

• tails = [1]
• tails = [1,4]
• tails = [1,4,5]
• tails = [1,2,5]
• tails = [1,2,3]
• tails = [1,2,3,7]
• tails = [0,2,3,7]

我们可以看到最后 tails 的长度是正确的，但是里面的值不正确，因为最后一步的替换破坏了子序列的性质。

Vue3 DOM Diff 核心算法

搞清楚了最长递增子序列这道算法题，我们再来看 Vue3 的 DOM Diff 核心算法就简单的多了。

我知道你已经迫不及待了，但是这里还是要插一句，如果你还不了解 React 以及 Vue2 的 DOM Diff 算法可以移步这个链接进行学习，循序渐进的学习可以让你更好的理解。

• Vue.js技术揭秘

回来后我们思考一个问题：Diff 算法的目的是什么？

为了减少 DOM 操作的性能开销，我们要尽可能的复用 DOM 元素。所以我们需要判断出是否有节点需要移动，应该如何移动以及找出那些需要被添加或删除的节点。

好了，进入正题，Vue3 DOM Diff 核心算法。

首先我们要搞清楚，核心算法的的位置。核心算法其实是当新旧 children 都是多个子节点的时候才会触发。

下面这段代码就是 Vue3 的 DOM Diff 核心算法，我加上了在源码中的路径，方便你查找。

// packages/runtime-core/src/renderer.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) / 2) | 0
        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 的作用就是找到那些不需要移动的元素，在遍历的过程中，我们可以直接跳过不进行其他操作。

其实这个算法的核心思想就是我们上面讲到的求解最长递增子序列的第二种解法，贪心 + 二分查找法。这也是为什么不着急说它的原因，因为如果你看懂了上面的 LeetCode 题解，你就已经掌握了 Vue3 的 DOM Diff 核心算法的思想啦。

不过，想要搞懂每一行代码的细节，还需放到 Vue3 整个 DOM Diff 的上下文中去才行。而且需要注意的是，上面代码中的 getSequence 方法的返回值与 LeetCode 题中所要求的返回值不同，getSequence 返回的是最长递增子序列的索引。上文我们曾提到过，使用贪心 + 二分查找替换的方式存在一些 Bug，可能会导致结果不正确。Vue3 把这个问题解决掉了，下面我们来一起看一下它是如何解决的。

// packages/runtime-core/src/renderer.ts
function getSequence(arr: number[]): number[] {
  const p = arr.slice() // 拷贝一个数组 p
  const result = [0]
  let i, j, u, v, c
  const len = arr.length
  for (i = 0; i < len; i++) {
    const arrI = arr[i]
    // 排除等于 0 的情况
    if (arrI !== 0) {
      j = result[result.length - 1]
      // 与最后一项进行比较
      if (arr[j] < arrI) { 
        p[i] = j // 最后一项与 p 对应的索引进行对应
        result.push(i)
        continue
      }
      // arrI 比 arr[j] 小，使用二分查找找到后替换它
      // 定义二分查找区间
      u = 0
      v = result.length - 1
      // 开启二分查找
      while (u < v) {
        // 取整得到当前位置
        c = ((u + v) / 2) | 0
        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 // 有可能替换会导致结果不正确，需要一个新数组 p 记录正确的结果
      }
    }
  }
  u = result.length
  v = result[u - 1]
  // 倒叙回溯 用 p 覆盖 result 进而找到最终正确的索引
  while (u-- > 0) {
    result[u] = v
    v = p[v]
  }
  return result
}

Vue3 通过拷贝一个数组，用来存储正确的结果，然后通过回溯赋值的方式解决了贪心 + 二分查找替换方式可能造成的值不正确的问题。

以上就是 Vue3 DOM Diff 的核心算法部分啦，欢迎光临前端食堂，客官您慢走～