Description
问题
手撕最长递增子序列以及 vue3 里的实现
前言
此处不讨论到 vue3 的 快速 diff 算法，只要记住三个步骤，顺着思路展开细节即可：
-
双端预处理
-
理想状态（新旧节点序列总有一个被处理掉）
- 根据剩下的那个序列做 新增 或 移除
-
非理想状态（中间对比），只要记住两点：
- 如何找到需要移动的节点以及如何移动
- 找到需要被添加或移除的节点并做对应操作
具体的设计思路可以去参考 HCY 的书籍，这里不做过多阐述。
但是很可能有人需要考验你的代码及算法功底，此时就会让你手撕一个 LIS（最长递增子序列）。
因此我这里对 LIS 的算法做一个补充笔记。
dp 算法
问题简化
我们先进行问题简化，不要求出 LIS，而是求出 LIS 的长度，可以参考 leetcode 的 300 题
后面的实现可以丢到 leetcode 中进行测试
算法
这里定义 dp[i] 为考虑前 i 个元素，以第 i 个数字结尾的 LIS 的长度，因此动转方程也就很好写了
dp[i] = max(dp[j]) + 1, j 区间是 [0, i) 且 nums[j] < nums[i]
var lengthOfLIS = function(nums) {
let dp = new Array(nums.length).fill(1)
for (let i = 0; i < nums.length; i++) {
for (let j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[i],dp[j]+1)
}
}
}
return Math.max(...dp)
};但是这个和 vue3 的 LIS 算法还相差甚远，而且它还是 O(n^2) 的肯定不能让人满意
贪心算法
前言
在想办法降低时间复杂度前，我们先想想能不能换个思路，用 贪心 来解决这个问题
贪心思路就是，如果我们要使 LIS 尽可能的长，那么就要让序列上升得尽可能慢，因此希望每次在子序列的末尾数字要尽可能小。
所以这里维护一个数组 d[i]，保存 nums 中的数字。 i 索引表示，在 i + 1 长度时候的 LIS 的末尾最小值
看不懂这个解释没关系，只需要记住一点，贪心算法中的数组，并没有保存完整的 LIS 序列，它只关心某个长度下末尾的最小值。具体可以看下面的例子理解
例子
以数组 [0,8,4,12,2] 为例，贪心会得到一个序列 [0, 2, 12]
d 序列存储的并非是最长递增子序列，而是对应 len 的末尾最小值，如果约束：
- 最长递增子序列的 len 为 1 时，找到对应的 0 索引：
[0,2,12]-> d[0] = 0，即如果 LIS 最长只能为 1，那么它的末尾元素一定为 0。对应的 LIS 为[0] - 最长递增子序列的 len 为 2 时，找到对应的 1 索引：
[0,2,12]-> d[1] = 2，即如果 LIS 最长只能为 2，那么它的末尾元素一定为 2。对应的 LIS 为[0,2] - 最长递增子序列的 len 为 3 时，找到对应的 2 索引：
[0,2,12]-> d[2] = 12，即如果 LIS 最长只能为 3，那么它的末尾元素一定为 12。对应的 LIS 为[0,4,12]
即贪心算法没有保留子序列，它只是保留了对应长度的最后一个数字
算法
算法的思路就是遍历 nums：
- 如果 nums[i] 大于 d的末尾元素，那么直接将 nums[i] push 进来
- 反之 nums[i] 一定可以替换掉 d 里的一个数字，找到那个数字并做替换
var lengthOfLIS = function(nums) {
if (!nums.length) return 0
let d = [nums[0]]
for (let i = 1; i < nums.length; i++) {
const numsI = nums[i]
if (numsI > d[d.length - 1]) {
// 塞进 d 末尾
d.push(numsI)
} else {
let j
for (j = 0; j < d.length; j++) {
if (numsI <= d[j]) {
// 找到可以替换的值
break
}
}
d[j] = numsI
}
}
return d.length
};但是此时贪心算法的时间复杂度还是 O(n^2) 并没有减少，别急，这时候我们看看有没有可以优化的点。我们发现在 d 序列中找可以替换的值时候，用了一个循环遍历了 d 序列，但是在之前例子中我们可以隐约感觉到 d 是 单调递增 的。
没错，d 确实是单调递增的，下个小节我给一个数学证明，不想看的跳过即可。利用 d 的 单调递增 性质可以使用 二分 找到想要替换的值。
数学证明
证明当 j < i 时, d[j] < d[i]
证明：
题设为 d[i] 表示一个长度为 i 的 LIS 的末尾最小元素
假设存在 j < i 时，d[j] >= d[i]
此时创造一个长度为 j 的 LIS 命名为序列 B，
该序列 B 由长度为 i 的 LIS 从末尾删除 i-j 个元素所构成
并设序列 B 的末尾元素为 x
由 LIS 特性可知: x < d[i]
又由假设可知: x < d[i] <= d[j] 即 x < d[j]
因此存在一个长度为 j 的序列 B, 其末尾元素 x < d[j]
与题设相矛盾, 得证 d[i] 具有单调性
贪心+二分
前言
这个算法中，我们仅仅是将贪心中 对 j 索引的搜索从遍历变成了二分，因此时间复杂度最终会变成 O(nlogn)。
但是注意一点，这次我将不再使用 d 数组来存储 nums 的值，而是使用 d 数组存储 nums 对应的 index 值，方便后续把 LIS 还原出来。思考一个问题，此时的 d[i] 将不再具备 单调递增 的性质，那还可以用二分搜索么？其实是没有问题的，第二层搜索的时候，实际变成了对 nums[d[i]] 的搜索，而 nums[d[i]] 依旧具备 单调递增 性质
算法
var lengthOfLIS = function (nums) {
if (!nums.length) return 0
let d = [0]
for (let i = 1; i < nums.length; i++) {
const numsI = nums[i]
if (numsI > nums[d[d.length - 1]]) {
d.push(i)
} else {
// 将搜索换成二分
// 选一个自己喜欢的二分即可
let l = 0
let r = d.length - 1
while (l <= r) {
let mid = (l + r) >> 1
if (numsI > nums[d[mid]]) {
l = mid + 1
} else {
r = mid - 1
}
}
d[l] = i
}
}
return d.length
}贪心+二分+路径回溯
前言
由于贪心算法只会保留当前长度的 LIS 下的末尾最小元素，因此我们需要使用一个 path 辅助数组
path[i] 存放了到达当前的 numsI 的 prevIndex
并且此时的实现，需要用 ts 来写，之后丢到 vue3 源码中使用尤大的测试来检验
实现
function getSequence(nums: number[]): number[] {
const path = nums.slice()
let d = [0]
for (let i = 1; i < nums.length; i++) {
const numsI = nums[i]
if (numsI > nums[d[d.length - 1]]) {
// 记录路径
// 是由当前的 d 末尾索引指向的元素到达的 numsI
path[i] = d[d.length - 1]
d.push(i)
} else {
let l = 0
let r = d.length - 1
while (l <= r) {
let mid = (l + r) >> 1
if (numsI > nums[d[mid]]) {
l = mid + 1
} else {
r = mid - 1
}
}
// 记录路径
// 使用 i 覆盖 d[l]
// 因此记录 path[i] 上一个索引为 d[l - 1]
path[i] = d[l - 1]
d[l] = i
}
}
// 反向恢复出正确的 LIS 索引数组
let prev = d[d.length - 1]
for (let i = d.length - 1; i >= 0; i--) {
d[i] = prev
// 通过 path 返回上一个 index
prev = path[prev]
}
return d
}edge case
到这里 getSequence 已经算实现的差不多了，我们回顾一下最开始的问题：
手撕最长递增子序列以及 vue3 里的实现
手撕已经完成了，但是 vue3 的实现和我们的手撕有什么区别么？可以看下面这个例子：
[2,0,1,3,4,5] 的 LIS 应该是 [0,1,3,4,5] 而对应的 index 结果应该为 [1,2,3,4,5]
但是如果你使用 vue3 的源码来执行上面的例子，就会发现结果为 [2,3,4,5]
function getSequence(arr: number[]): number[] {
const p = arr.slice()
// 凡事总有例外
// 由于 result 初始化会把 index 为 0 塞进去
// 如果 arr[0] === 0 的话会照样进入 result
const result = [0]
let i, j, u, v, c
const len = arr.length
for (i = 0; i < len; i++) {
const arrI = arr[i]
// 但是除了第一个元素为 0 的情况
// arr 中的 其他 0 是不参与 result 的构造的
if (arrI !== 0) {
// 省略构造 result 代码
}
}
// 省略恢复 result 数组代码
return result
}为什么构造 LIS 的时候不考虑 0 的情况呢？我们看下调用 getSequence 的情况在哪里
// moved 标记了存在需要移动的节点
// 如果存在那么就从 newIndexToOldIndexMap 中生成 LIS
// newIndexToOldIndexMap 是 新节点序列 index 和 旧节点序列 index 的索引
const increasingNewIndexSequence = moved
? getSequence(newIndexToOldIndexMap)
: EMPTY_ARR参考尤大的注释可以得知，0 是一种特殊的标记，标记了新增的节点
同时由于 offset +1 的存在，后面的代码也都会带有这个 offset，可以参见这一行
// works as Map<newIndex, oldIndex>
// Note that oldIndex is offset by +1
// and oldIndex = 0 is a special value indicating the new node has
// no corresponding old node.
// used for determining longest stable subsequence
const newIndexToOldIndexMap = new Array(toBePatched)
for (i = 0; i < toBePatched; i++) newIndexToOldIndexMap[i] = 0我们求出 LIS 的目的是为了找到哪些节点无需移动，而新增的节点根本不在节点移动的讨论范畴之内。
因此在 LIS 算法中，也无需考虑 0 的情况了。
tips: 关于尤大代码中的二分，可能会有人有疑惑不符合常见的二分模板，当 result 只有一个元素时，result.length 为 1，导致根本进不去二分的循环
u = 0
v = result.length - 1
while (u < v) { /* 省略部分 */ }其实不影响，进不去二分就进不去呗，result 如果只有一个元素进不去二分是不影响业务逻辑的。