最长递增子序列
什么是最长递增子序列
这里是 Wiki 对 最长递增子序列 的介绍
这里主要讲解 Vue3 在 Dom Diff 过程中使用的方法
点击展开 源码在此
typescript
// 输入一个数字数组
// 返回最长递增子序列对应的索引数组
function getSequence(arr: number[]): number[] {
// 创建一个副本作为指针数组
const p = arr.slice();
// 结果数组,先添加一个0作为起点
const result = [0];
let i, j, u, v, c;
// arr的长度
const len = arr.length;
// 遍历arr每个元素
for (i = 0; i < len; i++) {
// 当前元素
const arrI = arr[i];
// 如果当前元素不为0
if (arrI !== 0) {
// result最后一个元素的索引
j = result[result.length - 1];
// 如果当前元素大于result最后一个元素
if (arr[j] < arrI) {
// 设置指针为result最后一个元素索引
p[i] = j;
// 将当前i推入result
result.push(i);
// 跳过剩余逻辑
continue;
}
// 二分查找当前元素在result中的位置
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对应位置为当前i
result[u] = i;
}
}
}
// 从后向前遍历result和指针数组
u = result.length;
v = result[u - 1];
while (u-- > 0) {
// 一步步追溯前序最长子序列
result[u] = v;
v = p[v];
}
return result;
}解析
Vue3 在 Dom Diff 过程中使用 的 最长递增子序列,便利了 dom 的操作,极大的增加了效率.
使用算法
在上述代码中 使用到的 算法有 动态规划 二分查找 贪心算法 回溯修正
简要流程描述为
- 遍历 当前数组 判断其 是否大于 结果数组中最后一位
- 大于 最后一位,则添加到结果数组中,并记录当前索引值的前一位索引
- 不大于 的情况下 通过二分查找找到 大于的那一项 记录其索引值 并比较当前值 与原有值的大小
- 通过贪心算法 将小的值放入结果数组中
- 最后对循环的结果进行回溯修正,得出最后结果
举例说明
原数组 是 [1, 3, 10, 20, 30, 7, 8] 最长递增子序列 为 [1, 3, 10, 20, 30]初始状态
初始状态 默认将第一位放入到结果数组中
前五次循环
前五次循环 分别 判断 当前取值是否大于结果数组的最后一位,
大于直接添加
并在 回溯索引数组 中记录 上一位 索引值
后两次循环
后两次循环 分别 判断 当前取值是否大于结果数组的最后一位,
并不大于进行二分查找
索引是 5 (值为 7) 的时候通过 二分查找 7 < 10 找到 (值为 3 的) 索引值 1 将结果数组中 10 替换 7 并且在 回溯索引数组 中记录当前 上一位 索引为 1
索引是 6 (值为 8) 的时候通过 二分查找 8 < 20 找到 (值为 7 的) 索引值 5 将结果数组中 20 替换 8 并且在 回溯索引数组 中记录当前 上一位 索引为 5
回溯修正
最后的回溯修正 因在上述操作中 局部贪心算法 导致 会将小的值放入结果数组,可能影响结果 所以这边 回溯修正
索引值为 4 时 找到 回溯索引是 3 对应值为 20 这个值 与原来结果 8 不同 换为 20
索引值为 3 时 找到 回溯索引是 2 对应值为 10 这个值 与原来结果 7 不同 换为 10
索引值为 2 时 发现 回溯索引是 1 对应值为 3 直接覆盖
索引值为 1 索引值为 0 以 2 类推
总结
最终得出结果
遍历中 通过 动态规划 将 求最长递增 规划为 求当前位置最长 在通过 贪心算法 每次都将 相较小一点 的值 替换 大 的值 然后 二分查找 替换 最后通过 回溯修正 来处理 因为 局部贪心 导致 的 结果偏差