当前位置：首页 > article >正文

vue3-diff算法-最长递增子序列

article 2025/1/8 4:28:18

什么是最长递增子序列

最长递增子序列（LIS）是指在一个序列中，求出一个子序列，使得这个子序列元素的数值递增，且是原序列中长度最长的

vue3diff算法中的最长递增子序列

上篇文章分享vue3的diff算法原理最后一步处理其他情况（新增、卸载、移动）时提到一个关键点：最长递增子序列。
具体是怎么实现的呢？
demo:
在这里插入图片描述

在vue3是如何计算的？

整体思路

动态规划
二分查找
– 在一组有序数组中折半查找，提高效率
贪心算法
– 在每一步选择中都采取当前状态下最优选择的算法设计策略，旨在通过局部最优解的累积来获得全局最优解。
但可能会存在全局不是最优解的情况
回溯修正
– 为了解决贪心算法可能存在的问题。构造一个反向链表，每个节点记录上一个节点位置，最后回溯修正

以下demo为例：

第零位值为1，递增序列为0
在这里插入图片描述
第一位值为2，当时值大于前一个值，2 > 1，递增序列为1，前置指针0指向第0位，对应的值为1

第二位值为12，当时值大于前一个值，12 > 2，递增序列为2，前置指针1指向第1位，对应的值为2

第三位值为23，当时值大于前一个值，23 > 12，递增序列为3，前置指针2指向第2位，对应的值为12
在这里插入图片描述
第四位值为34，当时值大于前一个值，34> 23，递增序列为4，前置指针3指向第3位，对应的值为23

第五位值为3，当时值小于前一个值，3 < 34;
首先根据二分查找法：
首位0，末位4，中间位为2,，这时中间位对应的值12 > 当前值3。
这时首位还是0,末位变为2，中间位为1，中间位对应值2 < 当前值3。
这时首位值变为2，末位不变还是2。
二分查找结束
那这时候2这个位置放12 还是 3 呢？
根据贪心算法思路：
应该要放最小值 3，
记录下标索引为5。同时记录当前值3的前置指针为第一位，对应值2
在这里插入图片描述
第六位值为4，当时值小于前一个值，3 < 34;
思路同上：二分查找 + 贪心算法
3这个位置需要放4，
记录下标索引为6。同时记录当前值4的前置指针为第五位，对应值3

到这一步，有没有发现上面的递增序列是有问题的呢？
这是因为贪心算法导致的偏差。贪心算法只会考虑当前算法的最优解，不在乎全局是否是最优解。
这时候就需要最后一步，回溯修正

回溯修正
从结果序列最后一位开始，也就是序列4：34开始倒序往前回溯
序列4：当前值34，前置指针3对应的值是23,；因此我们把34的前一位修正为23，对应的序列索引为3
在这里插入图片描述
序列3：当前值23，前置指针2对应的值是12,；因此我们把23的前一位修正为12，对应的序列索引为2

序列2：当前值2，前置指针1对应的值是2；和原来一致，不动
序列1：当前值0，和原来一致，不动
最后可以得到最终的结果如下：
在这里插入图片描述
以上就是vue3-diff算法-最长递增子序列的一个大致过程；
源码如下：


```javascript
// 给定一个数组，求最长递增子序列
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  // 当前索引i替换原来位置
      }
    }
  }
  u = result.length
  v = result[u - 1]
  while (u-- > 0) { // 从后往前遍历，回溯修正
    result[u] = v
    v = p[v]
  }
  return result
}