博主首地址VUE3.0对diff过程进行了一次大升级，去掉了对下标key的搜索，改为可以移动dom的计算least程序，然后是domupdate，但是要想理解vue3.0中的diff算法，首先需要对最长递增子序列解法有一个基本的了解，因为vue是在它的基础上不断打磨改进的差异算法。求解最长递增子序列leetcode300给你一个整数数组nums，找出其中最长严格递增子序列的长度示例：输入：nums=[10,9,2,5,3,7,101,18]输出：4解释：最长递增子序列为[2,3,7,101]，所以长度为4动态规划：O(n2)定义：dp[i]表示以num[i]结尾的最长子序列的长度传递等式：双层遍历：比较num[i]和num[i]之前的数据，当num[i]>num[j]时，num[i]可以拼接在num[j]之后。此时num[i]位置的上升子序列的长度为：dp[i]+1当num[i]nums[j]){dp[i]=Math.max(dp[i],dp[j]+1)}}}returnMath.max(...dp)};计算过程图：贪心+二分查找：O(nlogn)要让上升子序列的长度尽可能长，就需要让序列的上升速度尽可能慢，所以需要使最后一个数在尽可能小的序列中。我们可以维护一个result数组来存放单调递增序列的结果，然后依次遍历nums数组；如果nums[i]>result[len]，直接插入到result的末尾；否则，在result数组中使用二分查找，找到第一个大于nums[i]的值result[j]；并更新result[j]=nums[i]functionlengthOfLIS(nums:number[]):number{constn=nums.lengthif(n<=1)returnn;letresult:number[]=[nums[0]]letlen=result.length//最大长度for(leti=1;iresult[len-1]){//大于结尾的值,直接靠近栈result.push(nums[i])++len}else{letleft=0,right=len;while(left>1if(result[mid]5->3之间是强绑定，7之前的绑定总会be都是5，5之前总会有3，如果这时候遇到4，栈就会变成3,4,7，虽然5变成了4，但是7->5->3的绑定关系会notchange如果此时再次遇到15，栈就变成了3,4,7,15，那么绑定回溯关系就变成了15->7->5->3，那么4什么时候生效呢？即4之后的值全部替换掉??。比如再次遇到6和8，栈就变成了3,4,6,8，绑定回溯关系就变成了8->6->4->3functiongetOfLIS(nums:number[]):number[]{constn=nums.lengthif(n<=1)returnnums;letresult:number[]=[0]//由原来存储具体值改为存储下标letchain=newMap()//通过下标存储映射关系for(leti=0;inums[j]){chain.set(i,{val:i,pre:j})result.push(i)}else{让left=0,right=result.length;while(left>1if(nums[result[mid]]0){//将找到的下标的前一位存储在pp[i]=result[u-1]}//找到下标并直接替换它result中的值result[u]=i}}}u=result.lengthv=result[u-1]//回溯，从最后一位开始，覆盖所有result，while(u-->0){result[u]=vv=p[v]}returnresult}参考Vue3DOMDiff核心算法分析wikipedia-longestincreasingsubsequence
