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

最长递增子序列是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$ 数组中的最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

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$ 大的数，然后替换掉。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

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$ 改为存储对应的索引：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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]$。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

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$ 为根，将这棵树画出来康康：

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

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

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

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

1
2
3
4
5
6
7

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源码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

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
}

参考

1. liweiwei1419的题解：https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/dong-tai-gui-hua-er-fen-cha-zhao-tan-xin-suan-fa-p/
2. Krahets的题解：https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/zui-chang-shang-sheng-zi-xu-lie-dong-tai-gui-hua-2/