最长递增子序列是Vue3中diff算法里面非常重要的一环,当发现有元素需要移动时,Vue便通过求取最长递增子序列,使得需要移动的元素数目最少。
题目链接:力扣题目:300. 最长递增子序列
动态规划的解法
对于这个问题,可以定义一个 d p dp d p 数组,其中 d p [ i ] dp[i] d p [ i ] 表示 n u m s [ i ] nums[i] n u m s [ i ] 为结尾的的最长递增子序列的长度。
要得到 n u m s [ i ] nums[i] n u m s [ i ] 为结尾的的最长递增子序列,只需要在 j ∈ [ 0 , i ) j \in [0,i) j ∈ [ 0 , i ) 中找到比 n u m s [ i ] nums[i] n u m s [ i ] 更小的数n u m s [ j ] nums[j] n u m s [ j ] ,然后将 n u m s [ i ] nums[i] n u m s [ i ] 接在这个数后面,就可以形成一个新的递增子序列。
这里的递增是严格递增,也就是说 n u m s [ j ] ≠ n u m s [ i ] nums[j]\not = nums[i] n u m s [ j ] = n u m s [ i ]
但是可能有多个 j j j 满足这个条件,我们只需要寻找 d p [ j ] dp[j] d p [ j ] 最大的时候,对应的 j j j 即可。
特别地,当 i = 0 i=0 i = 0 时,最长递增子序列的长度为 1 1 1 ,即 d p [ 0 ] = 1 dp[0]=1 d p [ 0 ] = 1 。
最后的结果便是 d p dp d p 数组中的最大值。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 var lengthOfLIS = function (nums ) { 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 ( N 2 ) O(N^2) O ( N 2 )
空间复杂度:O ( N ) O(N) O ( N )
进一步优化:定义一个新的状态
对于上面的算法来说,已经不方便优化了:
对于数组的遍历无法优化了
对于d p dp d p 的遍历也无法优化
所以,我们可以考虑重新设计一个状态:t a i l s tails t a i l s ,其中 t a i l s [ i ] tails[i] t a i l s [ i ] 表示长度为 i + 1 i+1 i + 1 的最长递增子序列中,最后一个元素。
不过, t a i l s [ i ] tails[i] t a i l s [ i ] 应该尽可能的小,因为越小的数字越容易被比它大的数字接在后面,这样也就更容易形成最长递增子序列了。(贪心策略)
这里很容易发现,t a i l s [ i ] tails[i] t a i l s [ i ] 也是递增的,我们可以简单用反证法证明一下(参考题解):
假设存在 i < j i<j i < j 使得 t a i l s [ i ] ≥ t a i l s [ j ] tails[i]\ge tails[j] t a i l s [ i ] ≥ t a i l s [ j ]
设此时 t a i l s [ i ] tails[i] t a i l s [ i ] 和 t a i l s [ j ] tails[j] t a i l s [ j ] 对应的最长递增子序列是 a a a 和 b b b ,那么:
t a i l s [ i ] = a [ i ] tails[i]=a[i] t a i l s [ i ] = a [ i ]
t a i l s [ j ] = b [ j ] tails[j]=b[j] t a i l s [ j ] = b [ j ]
由于 i < j i < j i < j 所以有 b [ i ] < b [ j ] b[i]<b[j] b [ i ] < b [ j ] ,即a [ i ] ≥ b [ j ] > b [ i ] a[i] \ge b[j] \gt b[i] a [ i ] ≥ b [ j ] > b [ i ]
但是,根据我们对 t a i l s [ i ] tails[i] t a i l s [ i ] 的定义,t a i l s [ i ] tails[i] t a i l s [ i ] 应该是 b [ i ] b[i] b [ i ] 而不是 a [ i ] a[i] a [ i ] ,所以这跟我们的定义矛盾。
此时 t a i l s tails t a i l s 的长度就是最长递增子序列的长度。
填充状态
通过刚刚的证明,可以发现 t a i l s tails t a i l s 是递增的,那么我们就可以使用二分查找来优化了。
我们定义最长递增子序列的长度 l e n = 0 len=0 l e n = 0 。遍历 n u m s nums n u m s 数组时,若当前正在遍历的元素为 n u m num n u m :
若 n u m > t a i l s [ l e n − 1 ] num > tails[len-1] n u m > t a i l s [ l e n − 1 ] ,那么就将 n u m num n u m 插入到 t a i l s tails t a i l s 的末尾,并更新 l e n + = 1 len+=1 l e n + = 1
若n u m = t a i l s [ l e n − 1 ] num = tails[len-1] n u m = t a i l s [ l e n − 1 ] ,那么什么都不做
否则进行二分查找,寻找 n u m num n u m 的右边界 r i g h t right r i g h t ,然后将 t a i l s [ r i g h t ] tails[right] t a i l s [ r i g h t ] 替换为 n u m num n u m
我们的 tails 要满足尽可能小的定义,所以我们需要把大的数换成小的,即寻找第一个比 n u m num n u m 大的数,然后替换掉。
理解了这个流程以后,我们可以写出算法的代码了:
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; } } return tails.length };
时间复杂度:O ( N log N ) O(N \log N) O ( N log N )
空间复杂度:O ( N ) O(N) O ( N )
求出序列
我们刚刚的做法仅仅是求出了这个最长递增子序列的长度,但是在 diff 算法中,我们需要求出这个子序列。
这个序列可能存在多个,我们只需求出一个即可。
首先需要注意的是,t a i l s tails t a i l s 并不是我们想要的序列,如果我们把 t a i l s tails t a i l s 改为存储对应的索引:
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 };
然后测试 n u m s = [ 2 , 3 , 1 , 5 , 6 , 8 , 7 , 9 , 4 ] nums=[2,3,1,5,6,8,7,9,4] n u m s = [ 2 , 3 , 1 , 5 , 6 , 8 , 7 , 9 , 4 ] ,结果发现输出了 [ 2 , 1 , 8 , 4 , 6 , 7 ] [2,1,8,4,6,7] [ 2 , 1 , 8 , 4 , 6 , 7 ] ,也就是说这个序列对应的下标并不是递增的,不符合最长递增子序列的定义。但是,t a i l s tails t a i l s 的最后一个元素是所得最长递增子序列的最后一个元素。
那么,我们如何得到这个序列呢,Vue的源码在修改 t a i l s [ i ] tails[i] t a i l s [ i ] 的时候,会将 t a i l s [ i − 1 ] tails[i-1] t a i l s [ i − 1 ] 作为 n u m s [ t a i l s [ i ] ] nums[tails[i]] n u m s [ t a i l s [ i ] ] 的父节点,也就是说,这构造了一个树,其中 n u m s [ i ] nums[i] n u m s [ i ] 对应的父节点为 p [ 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 };
还是刚刚的测试用例,我们得到 p p p 的数组是 [ u n d e f i n e d , 0 , u n d e f i n e d , 1 , 3 , 4 , 4 , 6 , 1 ] [ undefined, 0, undefined, 1, 3, 4, 4, 6, 1 ] [ u n d e f i n e d , 0 , u n d e f i n e d , 1 , 3 , 4 , 4 , 6 , 1 ]
我们以 u n d e f i n e d undefined u n d e f i n e d 为根,将这棵树画出来康康:
注:图中标注的是对应的值
从中我们可以发现一些规律:
每一层最右边的元素即为对应的 t a i l s tails t a i l s 元素。
最底层,最右边的元素是这个最长递增子序列中最大的元素。且可以通过 t a i l s [ t a i l s . l e n g t h − 1 ] tails[tails.length - 1] t a i l s [ t a i l s . l e n g t h − 1 ] 访问到。
沿着 t a i l s [ t a i l s . l e n g t h − 1 ] tails[tails.length - 1] t a i l s [ t a i l s . l e n g t h − 1 ] 向上遍历就可以得到整个最长递增子序列。
所以,我们只需要对 t a i l s tails t a i l s 进行一下处理就行了:
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] i--; }
时间复杂度:计算 t a i l s tails t a i l s 数组需要 O ( N log N ) O(N \log N) O ( N log N ) 的复杂度;在最坏情况下,这棵树退化成链表,因此遍历父节点需要 O ( N ) O(N) O ( N ) 的复杂度;一共需要 O ( N log N ) O(N \log N) O ( N log N ) 的时间复杂度。
空间复杂度:O ( 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 }
参考
liweiwei1419的题解:https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/dong-tai-gui-hua-er-fen-cha-zhao-tan-xin-suan-fa-p/
Krahets的题解:https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/zui-chang-shang-sheng-zi-xu-lie-dong-tai-gui-hua-2/