抱歉,您的浏览器无法访问本站

本页面需要浏览器支持(启用)JavaScript


了解详情 >

最长递增子序列是Vue3中diff算法里面非常重要的一环,当发现有元素需要移动时,Vue便通过求取最长递增子序列,使得需要移动的元素数目最少。

题目链接:力扣题目:300. 最长递增子序列

动态规划的解法

对于这个问题,可以定义一个 dpdp数组,其中 dp[i]dp[i] 表示 nums[i]nums[i] 为结尾的的最长递增子序列的长度。

要得到 nums[i]nums[i] 为结尾的的最长递增子序列,只需要在 j[0,i)j \in [0,i) 中找到比 nums[i]nums[i] 更小的数nums[j]nums[j],然后将 nums[i]nums[i] 接在这个数后面,就可以形成一个新的递增子序列。

这里的递增是严格递增,也就是说 nums[j]nums[i]nums[j]\not = nums[i]

但是可能有多个 jj 满足这个条件,我们只需要寻找 dp[j]dp[j] 最大的时候,对应的 jj 即可。

特别地,当 i=0i=0 时,最长递增子序列的长度为 11,即 dp[0]=1dp[0]=1

最后的结果便是 dpdp 数组中的最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var lengthOfLIS = function(nums) {
// dp[i] 前i个字符的最长递增子序列
// 如果 mums[j]<nums[i],那么dp[i]=Math.max(dp[j]+1,dp[i])
let dp = new Array(nums.length).fill(0);
dp[0]=1;
for (let i = 1; i < nums.length; i++) {
for (let j = 0; j < i; j++) {
if (nums[j] < nums[i]) {
dp[i] = Math.max(dp[j]+1,dp[i]);
}
}
}
return Math.max(...dp);
};
  • 时间复杂度:O(N2)O(N^2)
  • 空间复杂度:O(N)O(N)

进一步优化:定义一个新的状态

对于上面的算法来说,已经不方便优化了:

  • 对于数组的遍历无法优化了
  • 对于dpdp的遍历也无法优化

所以,我们可以考虑重新设计一个状态:tailstails,其中 tails[i]tails[i] 表示长度为 i+1i+1 的最长递增子序列中,最后一个元素。

不过, tails[i]tails[i] 应该尽可能的小,因为越小的数字越容易被比它大的数字接在后面,这样也就更容易形成最长递增子序列了。(贪心策略)

这里很容易发现,tails[i]tails[i] 也是递增的,我们可以简单用反证法证明一下(参考题解):


假设存在 i<ji<j 使得 tails[i]tails[j]tails[i]\ge tails[j]

设此时 tails[i]tails[i]tails[j]tails[j] 对应的最长递增子序列是 aabb,那么:

tails[i]=a[i]tails[i]=a[i]
tails[j]=b[j]tails[j]=b[j]

由于 i<ji < j 所以有 b[i]<b[j]b[i]<b[j],即a[i]b[j]>b[i]a[i] \ge b[j] \gt b[i]

但是,根据我们对 tails[i]tails[i] 的定义,tails[i]tails[i] 应该是 b[i]b[i] 而不是 a[i]a[i],所以这跟我们的定义矛盾。


此时 tailstails 的长度就是最长递增子序列的长度。

填充状态

通过刚刚的证明,可以发现 tailstails 是递增的,那么我们就可以使用二分查找来优化了。

我们定义最长递增子序列的长度 len=0len=0。遍历 numsnums 数组时,若当前正在遍历的元素为 numnum:

  • num>tails[len1]num > tails[len-1],那么就将 numnum 插入到 tailstails 的末尾,并更新 len+=1len+=1
  • num=tails[len1]num = tails[len-1],那么什么都不做
  • 否则进行二分查找,寻找 numnum 的右边界 rightright,然后将 tails[right]tails[right] 替换为 numnum

我们的 tails 要满足尽可能小的定义,所以我们需要把大的数换成小的,即寻找第一个比 numnum 大的数,然后替换掉。

理解了这个流程以后,我们可以写出算法的代码了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
var lengthOfLIS = function(nums) {
let tails = []
for (let num of nums) {
if (tails.length === 0 || num > tails[tails.length - 1]) {
tails.push(num)
}
else if (num === tails[tails.length - 1]) {
continue;
}
else {
let i = 0,j = tails.length;
while (i < j) { // 左闭右开的遍历
let mid = parseInt((i+j)/2);
if (tails[mid] < num) i=mid+1;
else j=mid;
}
tails[j] = num; // i=j
}
}
return tails.length
};
  • 时间复杂度:O(NlogN)O(N \log N)
  • 空间复杂度:O(N)O(N)

求出序列

我们刚刚的做法仅仅是求出了这个最长递增子序列的长度,但是在 diff 算法中,我们需要求出这个子序列。

这个序列可能存在多个,我们只需求出一个即可。

首先需要注意的是,tailstails 并不是我们想要的序列,如果我们把 tailstails 改为存储对应的索引:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
var lengthOfLIS = function(nums) {
let tails = []
for (let k of nums.keys()) {
let num = nums[k]
if (tails.length === 0 || num > nums[tails[tails.length - 1]]) {
tails.push(k)
}
else if (num === nums[tails[tails.length - 1]]) {
continue;
}
else {
let i = 0,j = tails.length;
while (i < j) {
let mid = parseInt((i+j)/2);
if (nums[tails[mid]] < num) i=mid+1;
else j=mid;
}
tails[j] = k;
}
}
console.log(tails)
return tails.length
};

然后测试 nums=[2,3,1,5,6,8,7,9,4]nums=[2,3,1,5,6,8,7,9,4],结果发现输出了 [2,1,8,4,6,7][2,1,8,4,6,7],也就是说这个序列对应的下标并不是递增的,不符合最长递增子序列的定义。但是,tailstails的最后一个元素是所得最长递增子序列的最后一个元素。

那么,我们如何得到这个序列呢,Vue的源码在修改 tails[i]tails[i] 的时候,会将 tails[i1]tails[i-1] 作为 nums[tails[i]]nums[tails[i]] 的父节点,也就是说,这构造了一个树,其中 nums[i]nums[i] 对应的父节点为 p[i]p[i]

我们基于上面的代码继续完善一下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
var lengthOfLIS = function(nums) {
let tails = []
let p = new Array(nums.length).fill(undefined)
for (let k of nums.keys()) {
let num = nums[k]
if (tails.length === 0 || num > nums[tails[tails.length - 1]]) {
p[k] = tails[tails.length - 1] // 记录位置
tails.push(k)
}
else if (num === nums[tails[tails.length - 1]]) {
continue;
}
else {
let i = 0,j = tails.length;
while (i < j) {
let mid = parseInt((i+j)/2);
if (nums[tails[mid]] < num) i=mid+1;
else j=mid;
}
tails[j] = k;
p[k] = tails[j-1]; // 记录位置
}
}
console.log(tails,p)
return tails.length
};

还是刚刚的测试用例,我们得到 pp 的数组是 [undefined,0,undefined,1,3,4,4,6,1][ undefined, 0, undefined, 1, 3, 4, 4, 6, 1 ]

我们以 undefinedundefined 为根,将这棵树画出来康康:

注:图中标注的是对应的值

从中我们可以发现一些规律:

  1. 每一层最右边的元素即为对应的 tailstails 元素。
  2. 最底层,最右边的元素是这个最长递增子序列中最大的元素。且可以通过 tails[tails.length1]tails[tails.length - 1] 访问到。
  3. 沿着 tails[tails.length1]tails[tails.length - 1] 向上遍历就可以得到整个最长递增子序列。

所以,我们只需要对 tailstails 进行一下处理就行了:

1
2
3
4
5
6
7
let i = tails.length - 1
let curr = tails[i]
while (i >= 0) {
tails[i]=curr
curr=p[curr] // curr是索引
i--;
}
  • 时间复杂度:计算 tailstails 数组需要 O(NlogN)O(N \log N) 的复杂度;在最坏情况下,这棵树退化成链表,因此遍历父节点需要 O(N)O(N) 的复杂度;一共需要 O(NlogN)O(N \log N) 的时间复杂度。
  • 空间复杂度:O(N)O(N)

Vue源码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
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; i < len; i++) {
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
}

参考

  1. liweiwei1419的题解:https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/dong-tai-gui-hua-er-fen-cha-zhao-tan-xin-suan-fa-p/
  2. Krahets的题解:https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/zui-chang-shang-sheng-zi-xu-lie-dong-tai-gui-hua-2/

评论