Vue3 diff的最长递增子序列 算法详解
const arr = [2, 1, 5, 3, 6, 4, 8, 9, 7]
function getSequence (arr) {
// const p = arr.slice() // [2, 1, 5, 3, 6, 4, 8, 9, 7]
const p = new Array(arr.length)
const result = [0]
let i, j, u, v, c
const len = arr.length // 9
for (i = 0; i < len; i++) {
const arrI = arr[i] // 某个元素
if (arrI !== 0) {
j = result[result.length - 1] // j是result中的最后一个元素 一开始是第0个元素
if (arr[j] < arrI) { // 如果arrI 大于 arr[j] 那么 把j存储到p[i]
// 存储在 result 更新前的最后一个索引的值
p[i] = j
result.push(i)
continue
}
u = 0 // result数组第0个元素
v = result.length - 1 // result数组的最后一个元素
// 二分搜索，查找比 arrI 小的节点，更新 result 的值
while (u < v) {
c = ((u + v) / 2) | 0
if (arr[result[c]] < arrI) {
u = c + 1
} else {
v = c
}
} // 最后的结果是找到u元素
if (arrI < arr[result[u]]) {
if (u > 0) {
p[i] = result[u - 1]
}
result[u] = i
}
}
}
u = result.length
v = result[u - 1]
// 回溯数组 p，找到最终的索引
while (u-- > 0) {
result[u] = v
v = p[v]
}
return result // 1 3 5 6 7
}
console.log(
// getSequence([5,3,4,0])
getSequence([2, 1, 5, 3, 6, 4, 8, 9, 7])
);
/*
。对于我们的例子而言，[2, 1, 5, 3, 6, 4, 8, 9, 7] 的最长子序列是 [1, 3, 4, 8, 9]，
而我们求解的 [1, 3 ,5 ,6 ,7] 就是最长子序列中元素在原数组中的下标所构成的新数组。
*/
// 2, 1, 5, 3, 6, 4, 8, 9, 7
//i
//1步 2
//2步 1
//3步 1 5 p[2] =1 result:[1,2]
//4步 1 3 p[3] =1 result:[1,3] 更新index为3这个位置的元素的时候，前一个比他小的元素index是1
//5步 1 3 6 p[4] =3 result:[1,3,4]
//6步 1 3 4 p[5] =3 result:[1,3,5] 更新index为5这个位置的元素的时候，前一个比他小的元素index是3
//7步 1 3 4 8 p[6] =5 result:[1,3,5,6] 更新index为6这个位置的元素的时候，前一个比他小的元素index是5
//8步 1 3 4 8 9 p[7] =6 result:[1,3,5,6,7] 更新index为7这个位置的元素的时候，前一个比他小的元素index是6
//9步 1 3 4 7 9 p[8] =5 result:[1,3,5,8,7]
// 操作结束后，result中的最后一个元素一定是最大子序列的最后一个元素，
// 但是前面的值不一定正确，比如第9步的时候7将8替换掉了，已经不满足子序列的条件了
// 所以需要数组p来记录 数组p中记录了第i次操作的时候，这次将要替换的元素的前一个元素（比它小的那个元素） 的index
// 最后进行一个回溯的操作
// 从result的最后一个元素开始，result中最后一个元素7肯定对应着最大子序列的最后一个，
// 去p数组中找，p数组中对应的这个元素，记录了更新index为7的时候的前一个比他小的元素的index
// 向前回溯去找