理解Vue3的最长递增子序列算法

Kaz

发布于：2022年3月19日

次浏览

字数：2.2k字

时长：10分钟

最长递增子序列是Vue3中diff算法里面非常重要的一环，当发现有元素需要移动时，Vue便通过求取最长递增子序列，使得需要移动的元素数目最少。

题目链接：力扣题目：300. 最长递增子序列

动态规划的解法

对于这个问题，可以定义一个 $dp$ 数组，其中 $dp[i]$ 表示 $nums[i]$ 为结尾的的最长递增子序列的长度。

要得到 $nums[i]$ 为结尾的的最长递增子序列，只需要在 $j \in [0,i)$ 中找到比 $nums[i]$ 更小的数 $nums[j]$ ，然后将 $nums[i]$ 接在这个数后面，就可以形成一个新的递增子序列。

这里的递增是严格递增，也就是说 $nums[j]\not = nums[i]$

但是可能有多个 $j$ 满足这个条件，我们只需要寻找 $dp[j]$ 最大的时候，对应的 $j$ 即可。

特别地，当 $i=0$ 时，最长递增子序列的长度为 $1$ ，即 $dp[0]=1$ 。

最后的结果便是 $dp$ 数组中的最大值。

var lengthOfLIS = function(nums) {
	// dp[i] 前i个字符的最长递增子序列
	// 如果 mums[j]<nums[i],那么dp[i]=Math.max(dp[j]+1,dp[i])
	let dp = new Array(nums.length).fill(0);
  dp[0]=1;
	for (let i = 1; i < nums.length; i++) {
		for (let j = 0; j < i; j++) {
			if (nums[j] < nums[i]) {
				dp[i] = Math.max(dp[j]+1,dp[i]);
			}
		}
	}
	return Math.max(...dp);
};

时间复杂度： $O(N^2)$
空间复杂度： $O(N)$

进一步优化：定义一个新的状态

对于上面的算法来说，已经不方便优化了：

对于数组的遍历无法优化了
对于 $dp$ 的遍历也无法优化

所以，我们可以考虑重新设计一个状态： $tails$ ，其中 $tails[i]$ 表示长度为 $i+1$ 的最长递增子序列中，最后一个元素。

不过， $tails[i]$ 应该尽可能的小，因为越小的数字越容易被比它大的数字接在后面，这样也就更容易形成最长递增子序列了。（贪心策略）

这里很容易发现， $tails[i]$ 也是递增的，我们可以简单用反证法证明一下（参考题解）：

假设存在 $i<j$ 使得 $tails[i]\ge tails[j]$

设此时 $tails[i]$ 和 $tails[j]$ 对应的最长递增子序列是 $a$ 和 $b$ ，那么：

$tails[i]=a[i]$
$tails[j]=b[j]$

由于 $i < j$ 所以有 $b[i]<b[j]$ ，即 $a[i] \ge b[j] \gt b[i]$

但是，根据我们对 $tails[i]$ 的定义， $tails[i]$ 应该是 $b[i]$ 而不是 $a[i]$ ，所以这跟我们的定义矛盾。

此时 $tails$ 的长度就是最长递增子序列的长度。

填充状态

通过刚刚的证明，可以发现 $tails$ 是递增的，那么我们就可以使用二分查找来优化了。

我们定义最长递增子序列的长度 $len=0$ 。遍历 $nums$ 数组时，若当前正在遍历的元素为 $num$ :

若 $num > tails[len-1]$ ，那么就将 $num$ 插入到 $tails$ 的末尾，并更新 $len+=1$
若 $num = tails[len-1]$ ，那么什么都不做
否则进行二分查找，寻找 $num$ 的右边界 $right$ ，然后将 $tails[right]$ 替换为 $num$

我们的 tails 要满足尽可能小的定义，所以我们需要把大的数换成小的，即寻找第一个比 $num$ 大的数，然后替换掉。

理解了这个流程以后，我们可以写出算法的代码了：

var lengthOfLIS = function(nums) {
    let tails = []
    for (let num of nums) {
        if (tails.length === 0 || num > tails[tails.length - 1]) {
            tails.push(num)
        }
        else if (num === tails[tails.length - 1]) {
            continue;
        }
        else {
            let i = 0,j = tails.length;
            while (i < j) { // 左闭右开的遍历
                let mid = parseInt((i+j)/2);
                if (tails[mid] < num) i=mid+1;
                else j=mid;
            } 
            tails[j] = num; // i=j
        }
    }
    return tails.length
};

时间复杂度： $O(N \log N)$
空间复杂度： $O(N)$

求出序列

我们刚刚的做法仅仅是求出了这个最长递增子序列的长度，但是在 diff 算法中，我们需要求出这个子序列。

这个序列可能存在多个，我们只需求出一个即可。

首先需要注意的是， $tails$ 并不是我们想要的序列，如果我们把 $tails$ 改为存储对应的索引：

var lengthOfLIS = function(nums) {
    let tails = []
    for (let k of nums.keys()) {
        let num = nums[k]
        if (tails.length === 0 || num > nums[tails[tails.length - 1]]) {
            tails.push(k)
        }
        else if (num === nums[tails[tails.length - 1]]) {
            continue;
        }
        else {
            let i = 0,j = tails.length;
            while (i < j) {
                let mid = parseInt((i+j)/2);
                if (nums[tails[mid]] < num) i=mid+1;
                else j=mid;
            } 
            tails[j] = k;
        }
    }
    console.log(tails)
    return tails.length
};

然后测试 $nums=[2,3,1,5,6,8,7,9,4]$ ，结果发现输出了 $[2,1,8,4,6,7]$ ，也就是说这个序列对应的下标并不是递增的，不符合最长递增子序列的定义。但是， $tails$ 的最后一个元素是所得最长递增子序列的最后一个元素。

那么，我们如何得到这个序列呢，Vue的源码在修改 $tails[i]$ 的时候，会将 $tails[i-1]$ 作为 $nums[tails[i]]$ 的父节点，也就是说，这构造了一个树，其中 $nums[i]$ 对应的父节点为 $p[i]$ 。

我们基于上面的代码继续完善一下：

var lengthOfLIS = function(nums) {
    let tails = []
    let p = new Array(nums.length).fill(undefined)
    for (let k of nums.keys()) {
        let num = nums[k]
        if (tails.length === 0 || num > nums[tails[tails.length - 1]]) {
            p[k] = tails[tails.length - 1]      // 记录位置      
            tails.push(k)
        }
        else if (num === nums[tails[tails.length - 1]]) {
            continue;
        }
        else {
            let i = 0,j = tails.length;
            while (i < j) {
                let mid = parseInt((i+j)/2);
                if (nums[tails[mid]] < num) i=mid+1;
                else j=mid;
            } 
            tails[j] = k;
            p[k] = tails[j-1]; // 记录位置
        }
    }
    console.log(tails,p)
    return tails.length
};

还是刚刚的测试用例，我们得到 $p$ 的数组是 $[ undefined, 0, undefined, 1, 3, 4, 4, 6, 1 ]$

我们以 $undefined$ 为根，将这棵树画出来康康：

注：图中标注的是对应的值

从中我们可以发现一些规律：

每一层最右边的元素即为对应的 $tails$ 元素。
最底层，最右边的元素是这个最长递增子序列中最大的元素。且可以通过 $tails[tails.length - 1]$ 访问到。
沿着 $tails[tails.length - 1]$ 向上遍历就可以得到整个最长递增子序列。

所以，我们只需要对 $tails$ 进行一下处理就行了：

let i = tails.length - 1
let curr = tails[i]
while (i >= 0) {
  tails[i]=curr
  curr=p[curr] // curr是索引
  i--;
}

时间复杂度：计算 $tails$ 数组需要 $O(N \log N)$ 的复杂度；在最坏情况下，这棵树退化成链表，因此遍历父节点需要 $O(N)$ 的复杂度；一共需要 $O(N \log N)$ 的时间复杂度。
空间复杂度： $O(N)$

Vue源码实现

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
}