Vue3.x中，为了以最小的性能开销完成DOM更新操作，应用3种Diff算法。其中的快速Diff算法，在比较新旧节点时，首先使用预处理，处理了是否需要DOM移动操作的简单情况---简单地挂载还是卸载节点。但对于复杂的情况，就需要计算出最长递增子序列--该序列中指向的节点为不需要移动的节点，用于辅助完成DOM移动操作。。。
何为最长递增子序列
在计算机科学中，最长递增子序列（longest increasing subsequence）问题是指，在一个给定的数值序列中，找到一个子序列，使得这个子序列元素的数值依次递增，并且这个子序列的长度尽可能地大。最长递增子序列中的元素在原序列中不一定是连续的--[维基百科](
最长递增子序列 - 维基百科，自由的百科全书 (wikipedia.org)
)
求解最长递增子序列的长度
对于给定的原始序列的最长递增子序列可能有多解，那Vue3的快速Diff算法中求解的最长递增子序列，是求解出所有的子序列，还是基于某种算法的一种解呢？值得注意的是，虽然满足条件的子序列可能有多种，但其长度确是相同的。即，最长递增子序列的长度的求解具有唯一性。所以我们先来解LeetCode上的一道算法题。
300.最长递增子序列
测试用例及思路讨论
求解使用的用例：[10, 9, 2, 5, 3, 7, 21, 18]
思路分析：如，维护一个空数组，遍历原数组，先放入10，然后，9小于10，不放入。。。依次判断。。。【误区！】
解法一：动态规划(O(N^2))
Copilot给出的解法。
* @param nums
* @returns number
* 复杂度分析
* 时间复杂度：O(n^2)
* 其中 n 为数组 nums 的长度，动态规划的状态数为 n，计算状态 dp
[i]
时，需要 O(n) 的时间遍历 dp
[0…i−1]
的所有状态
* 空间复杂度：O(n)
* 需要额外使用长度为 n 的 dp 数组
function lengthOfLIS(nums: number
[]
): number {
if (
nums.length
===
0
) return
0
// 动态规划，从大变小，每个元素都至少可以单独成为子序列，此时长度都为 1
// 声明数组dp，dp
[i]
的值代表 nums
[i]
结尾的最长子序列长度
let dp: number
[]
= new Array(nums.length).fill(1)
for (let
i
=
1
for (let
j
=
0
// 如果nums
[i]
大于nums
[j]
，nums
[i]
可以接在 nums
[j]
之后（因为要求严格递增【排除了相等等情况】），此情况下最长子序列长度为 dp
[j]
+ 1
if (nums
[j]
< nums
[i]
) {
dp
[i]
= Math.max(dp
[i]
, dp
[j]
+ 1)
return Math.max(...dp)
打断点分析
* @Description: 贪心算法（尽可能小的值的一个一个放入）+二分查找
* 分析可优化方案（O(N^2)数据大时，低性能很明显）：
* 动态规划中，通过线性遍历来计算 dp 的复杂度无法降低
* 如果，我们要使子序列尽可能的长，则需要让序列递增得尽可能慢，因此我们希望每次在上升子序列最后加上的那个数尽可能的小，同时要做到比较的过程复杂度低于O(N)
* 故需要维护，不同长度时的子序列的最后元素（其目的用于比较）构成的数组，遍历原数组（O(N)）使用二分查找(O(logN))来找到最合适的位置进行替换---保证子序列尽可能慢的递增
* @Author: ljy
* @Date: 2022-05-03 12:43:19
* @LastEditors: ljy
* @LastEditTime: 2022-05-09 01:51:24
* @FilePath: \longest-increasing-subsequence\lengthByDichotomy.ts
* @param nums
* @returns
* 复杂度分析
* 时间复杂度：O(nlogn)
* 遍历 nums 列表需 O(N)，在每个 nums
[i]
二分法需 O(logN)
* 空间复杂度：O(n)
* tails需要额外空间
function lengthByDichotomy(nums: number
[]
): number {
if (
nums.length
===
0
) return
0
// 维护一个数组 tails，其中每个元素 tails
[k]
的值代表 长度为 k+1 的子序列尾部元素的值（k为自然数）
// 如tail
[0]
是求长度为1的连续子序列时的最小末尾元素
// 例：在 1 8 4中 tail
[0]
=1 tail
[1]
=4 没有tail
[2]
因为无法到达长度为3的连续子序列
// 初始tails数组
[0]
,其值为子序列列长度为1，即num
[0]
// 由于js数组的特点，可以不用初始化tails数组的长度，不用每个元素都初始化0---当然初始化也是可以的
let tails: number
[]
=
[nums[0]]
// 设 result 为 tails 当前长度，代表直到当前的最长递增子序列长度
let
result
=
1
// 从nums第二个元素开始遍历数组
for (let
i
=
1
// 比 tails
[result]
大，则更新 tails
[result]
，同时 result++
if (nums
[i]
> tails
[result-1]
) {
tails
[++result - 1]
= nums
[i]
} else {
// 否则，使用二分查找法，找到比 nums
[i]
大的最小的 tails
[j]
，即tails
[j]
<nums
[i]
<tails
[j+1]
，然后更新 tails
[j]
let
left
=
0
, right = result
while (left < right) {
const
mid
= (left + right) >>
1
if (tails
[mid]
< nums
[i]
) {
left
= mid +
1
} else {
right
= mid
tails
[left]
= nums
[i]
// 打印tails数组---不能等同于不同长度时对应的子序列，因为遇到小的数，会插在更前面，改变了在元素组的位置（证明用例
[10, 9, 2, 5, 3, 7, 1, 18]
中的1插入时）
// console.log(tails)
return result
打断点分析
Vue3快速Diff算法中的实现
注意：在快速Diff算法中，求解最长递增子序列的目的是对子节点重新编号，所以肯定不只是求解出长度即可。
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
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
分析：getSequence相比于解法二，思路相近。但除了求解出长度，还会回溯查找原数组的索引--通过维护数组p，p记录了当前位置元素arr[i]插入时，递增序列前一个元素的真实值。
Vue3的快速Diff算法中，利用贪心算法求解最长递增子序列，而不是求解所有的可能。出道算法题：给一个整数的数组，求解其所有可能的最长递增子序列。参考LeetCode 673
PS：推荐一个VScode插件--Vscode Google Translate，查看框架源码等api时自动翻译注释。
