Vue3 最长递增子序列研究

本文初衷

彻底讲清楚 Vue3 源码中实现最长递增子序列的算法。

概念名词

**最长递增子序列：**在一个给定的数值序列中，找到一个子序列，使得这个子序列元素的数值依次递增，并且这个子序列的长度尽可能地大。最长递增子序列中的元素在原序列中不一定是连续的。

比如：

序列 [10, 9, 2, 5, 3, 7, 101, 18] 的最长递增子序列是 [2, 3, 7, 101] 或 [2, 3, 7, 18]。

序列 [3, 2, 8, 9, 5, 6, 7, 11, 15, 4] 的最长递增子序列是 [2, 5, 6, 7, 11, 15]

Vue3 使用最长递增子序列的背景

在 《Vue.js 设计与实现》第 11 章我们了解到 Vue3 在进行新子节点和旧子节点 DOM Diff 的方式是，先同步头部节点（处理相同的前置元素），再同步尾部节点（处理相同的后置元素），接下来判断哪些子节点需要移动，并且处理如何移动。

在处理子节点如何移动的问题上，使用了最长递增子序列。

为什么要用最长递增子序列?

（这段描述摘自：黄轶《Vue.js 3.0 核心源码解析》）

举个简单的例子具体看一下

var prev = [1, 2, 3, 4, 5, 6]

var next = [1, 3, 2, 6, 4, 5]

从 prev 变成 next，数组里的一些元素的顺序发生了变化，我们可以把子节点类比为元素，现在问题就简化为我们如何用最少的移动使元素顺序从 prev 变化为 next 。

一种思路是在 next 中找到一个递增子序列，比如 [1, 3, 6] 、[1, 2, 4, 5]。之后对 next 数组进行倒序遍历，移动所有不在递增序列中的元素即可。

如果选择了 [1, 3, 6] 作为递增子序列，那么在倒序遍历的过程中，遇到 6、3、1 不动，遇到 5、4、2 移动即可，如下图所示：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-3TXtDhk2-1648818081393)(https://s3-us-west-2.amazonaws.com/secure.notion-static.com/4ba50123-4734-445e-b7b7-48bdbe112546/Untitled.png)]

如果选择了 [1, 2, 4, 5] 作为递增子序列，那么在倒序遍历的过程中，遇到 5、4、2、1 不动，遇到 6、3 移动即可，如下图所示：

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-DQosxXrD-1648818081395)(https://s3-us-west-2.amazonaws.com/secure.notion-static.com/2ec300e0-659f-4176-bbdd-2f7cc31b5d96/Untitled.png)]

可以看到第一种移动了三次，而第二种只移动了两次，递增子序列越长，所需要移动元素的次数越少，所以如何移动的问题就回到了求解最长递增子序列的问题。

实现最长递增子序列

需要明确的是，我们现在要做的是实现 Vue3 DOM Diff 中的最长递增子序列，这和力扣题库中的 300. 最长递增子序列 有些差别。力扣题求解的是最长递增子序列的长度，我们的 getRequence 函数返回值是一个下标数组。但实现方式上都是采用 贪心 + 二分查找。

给定数组 [3, 2, 8, 9, 5, 6, 7, 11, 15, 4]，求解该数组的最长递增子序列？

肉眼可见，该数组最长递增子序列为 [2, 5, 6, 7, 11, 15]，对应下标数组为 [ 1, 4, 5, 6, 7, 8 ]

再次提醒，我们函数返回值是：下标数组

function getRequence(arr) {

}

const data = [3, 2, 8, 9, 5, 6, 7, 11, 15, 4];
const res = getRequence(data);

console.log('下标: ', res); // 期望输出：[ 1, 4, 5, 6, 7, 8 ] 输出的是*最长递增子序列的下标*
console.log('长度: ', res.length); // 期望输出： 6

这道题是一道中等复杂程度题目，但你不用担心，我们理清思路，其实也很简单。

1. 构建一个下标数组，保证下标对应的元素在原数组中是递增的

function getRequence(arr) {
  const length = arr.length;

  // 描述最长递增子序列的数组，元素是递增元素对应的下标
  const result = [0];
  // result 最后一个元素
  let resultLast;

  for (let i = 0; i < length; i++) {
    const arrI = arr[i];

    // 在 Vue 3 Diff 中，0 表示该新节点不在旧节点的中，是需要进行新增的节点
    if (arrI !== 0) {
      resultLast = result[result.length - 1];

      if (arrI > arr[resultLast]) {
        result.push(i);
        continue;
      }
    }
  }

  return result;
}

const data = [3, 2, 8, 9, 5, 6, 7, 11, 15, 4];

const res = getRequence(data);

console.log('下标: ', res); 
console.log('长度: ', res.length);

// 下标:  [ 0, 2, 3, 7, 8 ]
// 长度:  5

可以看到，首先定义了一个 result 数组，它是用于描述最长递增子序列元素在原数组对应的下标数组。然后定义了一个循环，循环中排除了元素值为 0 的情况，因为 0 在 dom diff 中是需要新增的子节点，此时我们考虑的是元素移动的情况。接下来，将当前元素与子序列最后一个元素对应的原数组的元素进行比较，如果当前元素更大，则将下标 push 进 result。

这样目前可以保证 result 数组中保存的下标是递增的，[ 0, 2, 3, 7, 8 ]，但是所对应的元素值为 [3, 8, 9, 11, 15]，长度为 5，很明显，2 比 3更小，可以求解更长的递增子序列 [2, 5, 6, 7, 11, 15]，长度为 6

接下来，我们通过二分查找保证最长递增子序列长度正确

2. 构建一个正确长度的最长递增子序列，只需要保证数组长度正确即可

function getRequence(arr) {
  const length = arr.length;

  // 描述最长递增子序列的数组，元素是递增元素对应的下标
  const result = [0];
  // result 最后一个元素
  let resultLast;

+  let start;
+  let end;
+  let middle;

  for (let i = 0; i < length; i++) {
    const arrI = arr[i];

    // 在 Vue 3 Diff 中，0 表示该新节点不在旧节点的中，是需要进行新增的节点
    if (arrI !== 0) {
      resultLast = result[result.length - 1];

      if (arrI > arr[resultLast]) {
        result.push(i);
        continue;
      }

+      start = 0;
+      end = result.length - 1;
+
+      while (start < end) {
+        middle = ((start + end) / 2) | 0; // 或者 middle = Math.floor((start + end) / 2);
+
+        if (arr[result[middle]] < arrI) {
+          start = middle + 1;
+        } else {
+          end = middle;
+        }
+      }
+
+      // while 循环结束后，start 和 end 会指向同一个元素
+      if (arr[result[end]] > arrI) {
+        result[end] = i;
+      }
    }
  }

  return result;
}

const data = [3, 2, 8, 9, 5, 6, 7, 11, 15, 4];

const res = getRequence(data);

console.log('下标: ', res);
console.log('长度: ', res.length);

// 下标:  [ 1, 9, 5, 6, 7, 8 ]，对应的arr中元素是 [2, 4, 6, 7, 11, 15]
// 长度:  6

可以看到，我们定义了 start，end 和 middle 三个指针，不断进行二分查询，中间元素 middle 小于 arrI，说明 arrI 较大，区间换成[middle + 1, end]; 否则说明，中间元素 middle 大于等于 arrI，说明 arrI 较小，区间换成 [start, middle]， 如此循环，直至 start ≥ end 为止，二分找到某一项刚好大于当前项，此时 start 和 end 指针应该是指向同一个元素下标，然后用当前元素替换掉二分找到的那一项。

result 数组下标变化过程（使用 arr 数组元素描述，这样更清晰一点）

// 3
// 2
// 2 8 
// 2 8 9
// 2 5 9
// 2 5 6
// 2 5 6 7
// 2 5 6 7 11
// 2 5 6 7 11 15
// 2 4 6 7 11 15

在我们的例子中，需要在数组 [2, 5, 6, 7, 11, 15] 中找到 4 应该放入的位置，需要对数组进行二分查找， start: 0, end: 6, middle: 3, 然后使用 while 不断二分查询，最终找到替换元素是 5，然后用 4替换掉 5。

很明显，4 替换 5 明显是错误的，因为最长递增子序列的顺序不能颠倒。

3. 回溯：使用前驱索引纠正最长递增子序列的偏差

回溯这个过程需要定义一个与原数组相同长度的数组 p，数组每一项保存应该排在当前元素前面元素的下标。然后经过逆序遍历数组 p，纠正 result 数组的元素。

可能文字表述有些复杂，我们画个图解释一下：

result 数组下表变化过程（使用 arr 数组元素描述，这样更清晰一点）

// 3
// 2
// 2 8 
// 2 8 9
// 2 5 9
// 2 5 6
// 2 5 6 7
// 2 5 6 7 11
// 2 5 6 7 11 15

在数组 result 组建过程中，我们用 p 数组保存当前 result 的前一项的索引。

function getRequence(arr) {
  const length = arr.length;

  // 描述最长递增子序列的数组，元素是递增元素对应的下标
  const result = [0];
  // result 最后一个元素
  let resultLast;

  let start;
  let end;
  let middle;

+  let p = arr.slice();

  for (let i = 0; i < length; i++) {
    const arrI = arr[i];

    // 在 Vue 3 Diff 中，0 表示该新节点不在旧节点的中，是需要进行新增的节点
    if (arrI !== 0) {
      resultLast = result[result.length - 1];

      if (arrI > arr[resultLast]) {
        result.push(i);
+        p[i] = resultLast;

        continue;
      }

      start = 0;
      end = result.length - 1;

      while (start < end) {
        middle = ((start + end) / 2) | 0; // 或者 middle = Math.floor((start + end) / 2);

        if (arr[result[middle]] < arrI) {
          start = middle + 1;
        } else {
          end = middle;
        }
      }

      // while 循环结束后，start 和 end 会指向同一个元素
      if (arr[result[end]] > arrI) {
        result[end] = i;
+        p[i] = result[end - 1];
      }
    }
  }

+  let i = result.length;
+  let last = result[i - 1];
+
+  while (i-- > 0) {
+    result[i] = last;
+   last = p[last];
+  }

  return result;
}

const data = [3, 2, 8, 9, 5, 6, 7, 11, 15, 4];

const res = getRequence(data);

console.log('下标: ', res);
console.log('长度: ', res.length);

// 下标:  [ 1, 4, 5, 6, 7, 8 ]
// 长度:  6

定义了数组 p 长度与 arr 数组长度保持一致，p[i] 是描述应该在当前元素前面元素的下标，方便回溯时纠正第 2 步生成的有问题的 result 数组。result 数组中最后一项肯定是正确的下标位置，我们通过 p 数组不断迭代，修正 result 中存储下标错误的问题。

目录

题目：

输入描述:

输出描述:

示例1

输入

输出

示例2

输入

输出

说明

备注:

思路分析：

改进：

得到最长子序列：

易错点：

代码展示：

题目：

给定数组arr，设长度为n，输出arr的最长递增子序列。（如果有多个答案，请输出其中字典序最小的）

输入描述:

输出两行，第一行包括一个正整数n（n<=100000），代表数组长度。第二行包括n个整数，代表数组arr 。 (1 ≤ arr[i] ≤ 1e9)

输出描述:

输出一行。代表你求出的最长的递增子序列。

示例1

输入

9 2 1 5 3 6 4 8 9 7

输出

1 3 4 8 9

示例2

输入

5 1 2 8 6 4

输出

1 2 4

说明

其最长递增子序列有3个，（1，2，8）、（1，2，6）、（1，2，4）其中第三个字典序最小，故答案为（1，2，4）

备注:

时间复杂度O(NlogN)，空间复杂度O(N)。

思路分析：

1. 由递增子序列，可以知道该序列是依赖与前面序列，且连续性要求较高
   1. 所以dp[i]存储的值是以array[i]元素结尾时的最优解，即最长递增子序列
2. dp[i]点最长子序列依赖于所有array[小于i的值]的dp[]值中的最大值
   1. 比如array = {1,3,5,4,6,5,7}
   2. dp[]的前三位是{1,2,3} 则第dp[3]，
   3. 查到array[0]
   4. 而dp[1]>dp[0] 所以将dp[3]赋值为dp[1]+1,因为前三位中有个长度为2的序列的结尾数比array[3]小
3. 依次更新dp,找到dp的最大值，即为最长递增子序列的长度

改进：

1. 每次求dp都要遍历一次array的前面部分，导致时间复杂度时O(N^2)
2. 但是之前的array与dp已经遍历过了，现在我们要做的是将其中重要的信息存储起来
   1. 重要信息:长度为0/1/2/3的子序列，最小要以什么array结尾
   2. 每次dp的更新就不需要去遍历所有array，
      1. 需要查找到合适的结尾数，在其基础上将序列长度加一。并根据当前dp，array更新“重要信息”
   3. 序列长度，与结尾数的映射一定是单调递增的，所以，查找时，可以用二分查找，或者用有序表来组织（ceilingKey()方法）

得到最长子序列：

1. 根据dp，dp存储的是以dp[i]结尾时的最长子序列长度，
2. 那么倒序遍历dp，当dp[i]的值等于len,len-1,len-2....时说明是最长子序列的最小字典序

易错点：

1. 在用有序表TreeMap时，如果要将（键1，值1）替换成（键2，值1)，不能单纯使用replace，put方法，要先remove（键1，值1），再put(键2，值1)

代码展示：

import java.io.*;
import java.util.TreeMap;

public class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(read.readLine());
        String[] str = read.readLine().split(" ");
        int dp[] = new int[n];//以array[i]结尾的序列的最长长度
        int array[] = new int[n];

        for(int i=0;i<n;i++){
            array[i] = Integer.parseInt(str[i]);
            dp[i] = 0;
        }
        
        int max = 0;//最长子序列长度
        int flag = 0;//当前最长序列
        TreeMap<Integer,Integer> map = new  TreeMap<Integer,Integer>();//（长度为i的最小结尾数, 序列长度i)
        for(int i=0;i<n;i++){
            Integer key = map.ceilingKey(array[i]);
            if(key == null){//没找到ceiling，说明当前array是最大的，添加一个键值对，序列长度加1
                map.put(array[i],++flag);
                dp[i] = flag;
            }else{//找了，更新，（键1，值1）替换成（键2，值1)
                dp[i] = map.get(key);
                map.remove(key);
                map.put(array[i],dp[i]);
            }
            max = Math.max(max, dp[i]);

        }
        //System.out.println(max);
        
        String sout = "";
        for(int j = n-1;j>=0;j--){//倒序遍历，遇到len,len-1,len-1...将其加入字符串
            if(dp[j] == max){
                sout =  array[j]+" "+sout ;
                max--;
            }
        }
        
        System.out.print(sout);
        
    }
}