关于javascript:最长递增子序列及vue30中diff算法

VUE3.0 对 diff 过程进行了大降级，去掉了针对下标 key 的查找，而是变成了计算能够起码挪动 dom 的计划，而后在进行 dom 更新，而要想看懂 vue3.0 中 diff 算法，首先须要先对 最长递增子序列 的求解有一个根本的理解，因为 vue 就是在它的根底上来一直打磨、欠缺的 diff 算法。

给你一个整数数组 nums，找到其中最长严格递增子序列的长度
示例:

输出：nums = [10, 9, 2, 5, 3, 7, 101, 18]
输入：4
解释：最长递增子序列是 [2, 3, 7, 101]，因而长度为 4。

定义：dp[i]代表以 num[i]结尾的最长子序列的长度
转移方程：

双层遍历：比照 num[i]和 num[i]之前的数据
当 num[i]>num[j] 时，num[i]就能够拼接在 num[j]后，此时 num[i]地位的回升子序列长度为：dp[i]+1
当 num[i]<num[j] 时，num[i]和 num[j]无奈形成回升子序列，跳过
计算出 dp[i] 中最大的值即为计算结果

function lengthOfLIS(nums: number[]): number {
  const len:number = nums.length
  if (len <=1) return len;
  let dp:number[] = new Array(len).fill(1)
  for (let i = 0; i < nums.length; i++) {for (let j = 0; j < i; j++) {if (nums[i] > nums[j]) {dp[i] = Math.max(dp[i], dp[j] + 1)
      }
    }
  }
  return Math.max(...dp)
};

计算过程图：

要使回升子序列的长度尽可能的长，就要使序列回升的速度尽可能的慢，因而须要让序列内开端数字尽可能的小。
咱们能够保护一个 result 数组，用来寄存枯燥递增序列后果，而后顺次遍历 nums 数组；

如果nums[i] > result[len], 则直接插入到result 开端

否则，在 result 数组中通过 二分查找 的形式，找到第一个比 nums[i] 大的值result[j]; 并更新result[j] = nums[i]

function lengthOfLIS(nums: number[]): number {
const n = nums.length
if (n <=1) return n;
let result:number[] = [nums[0]]
let len = result.length    // 最大长度
for (let i = 1; i < n; i++) {if (nums[i] > result[len-1]) { // 大于开端的值，间接近栈
    result.push(nums[i]) 
    ++len
  } else {
    let left = 0, right = len;
    while(left < right) {// 二分查找序列内第一个大于 nums[i]的值
      const mid = (left + right) >> 1
      if (result[mid] < nums[i]) {left = mid + 1} else {right = mid}
    }
    result[left] = nums[i] // 替换
  }
}
return len
}

计算过程图：

留神：这个计划中的 result 失去的长度是正确的，然而程序并不一定是正确后果须要的程序，比方 [10, 9, 2, 5, 3, 7, 1, 18] 失去的 result 为[1, 3, 7, 18]，

那么为什么贪婪算法能够失去正确的长度呢？

要想得到最长回升子序列的正确长度，首先必须保障 result 内寄存的数值增速尽可能稳和慢，所以要应用增长空间大、有后劲的值来组合；

比方 1,50,5,…… 当咱们遍历到 50 的时候，并不知道前面是否还有值，此时先将数据放入栈中存起来是理智的，持续往后遍历遇到了 5，显然选用1,5 比选用 1,50 更让人释怀也更有后劲，因为前面的数再往栈内寄存的几率更大，即便前面没有更多值了，那么选用 1,5 还是 1,50 其实最初长度是一样的。

那如果应用了更小的值，曾经在栈内的值应该如何解决呢？比方咱们栈中寄存了 1,3,9,10, 再往后遍历的时候遇到了5，显然5 比9,10都更有后劲，如果将栈间接变成 1,3,5 又不太可能，因为如果前面没有更多值了，长度由 4 变成 3，后果是谬误的；但如果不去管5 的话，前面又碰到了 6,7,8那不就 JJ 了；

所以咱们能够思考既不能放弃有后劲的值，也不能错失正确的长度后果，因而咱们无妨鱼和熊掌都兼得一下，比方将第一个大于 5 的值 9 替换掉变成1,3,5,10，这样在放弃栈内容程序正确性的状况下保障了栈长度的正确性，接下来，再往后遍历会遇到 3 种状况：

前面没有更多值了，此时后果长度为4，是没问题的
如果前面遇到 50，则能够直接插入到栈中，变为1,3,5,10,50，长度为5 也是没问题的，因为咱们并没有将最初的值替换掉，所以咱们能够将栈设想成为 9 做了个替身5，真正的值还是替换前的1,3,9,10
如果前面遇到了 6，则依照一开始的规定，将10 替换掉变成 1,3,5,6，长度为4 也是没问题的，因为咱们将最初的值都做了替换，所以此时替身 5 就变成了真身，同时咱们也发现，失去的栈中的值就是最初的最优解

能够发现，在没有替换完栈中的值时，栈 中被替换的的值，起到的是占位的成果，为前面遍历数字提供参照的作用；

要想得到正确的序列，首先要对下面的代码做一些改变：

将 result 批改为存储下标（最初回溯是会改成真正的值）；为上面的 chain 提供参考
减少 chain 变量，寄存每一位在被退出到 result 时其对应的前一位的下标值，进行关系绑定
回溯 chain，笼罩result 的值。因为 result 内，最初一位肯定是正确的，所以能够从后往前进行修改

下面咱们说过在对栈内某个值进行替换后，变动的值前面的所有的值如果都没有变过的话，那么替换的值只是一个替身，无奈作为最初后果进行输入，只有替换值前面的都变动过了，才会由替身变为真身。那么在没有全副替换前，咱们是须要有一种办法去保留原来程序的：

比方 3,5,7，能够设想成7->5->3 他们之间是强绑定，7后面绑定的永远都是 5，5 后面永远都是3

如果此时遇到了 4，栈会变成3,4,7，5 尽管变成了 4，然而7->5->3 这个绑定关系是不会变的
如果此时又遇到了15，栈变成了3,4,7,15，则绑定和回溯关系就变成了15->7->5->3

那么什么时候 4 能失效呢？那就是在 4 前面的值都被替换了，比方又遇到了 6 和8，则栈变为了3，4，6，8, 绑定和回溯关系就变成了8->6->4->3

function getOfLIS(nums: number[]):number[]  {
  const n = nums.length
  if (n <=1) return nums;
  let result:number[] = [0]  // 由原来存储具体值改为存储下标
  let chain = new Map() // 通过下标存储映射关系
  for (let i = 0; i < n; i++) {const j = result[result.length - 1]
    if (nums[i] > nums[j]) {chain.set(i,{val: i, pre: j})
      result.push(i)
    } else {
      let left = 0, right = result.length;
      while(left < right) {const mid = (left + right) >> 1
        if (nums[result[mid]] < nums[i]) {left = mid + 1} else {right = mid}
      }
      chain.set(i,{val: i, pre: result[left - 1]})
      result[left] = i
    }
  }
  let preIdx = result[result.length - 1]
  let len = result.length
 // 从后往前进行回溯，修改笼罩 result 中的值，找到正确的程序
  while(chain.get(preIdx)) {let lastObj = chain.get(preIdx)  
    result[--len] = nums[lastObj.val]
    preIdx = lastObj.pre
  }
  return result
}; 

const test= [9,2,5,3,7,101,4,18,1]
console.log(getOfLIS(test)); // [2,3,4,18]

vue3 中的 diff 和下面的思维其实是一样的，都是基于下标来绑定数字在被插入 result 内时和其后面一个数字的关系。然而它看起来会更加难以了解，因为它是通过 数组（P）来绑定回溯关系的，返回的是最长递增子序列的下标值

  function getSequence(arr) {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]
      // 排除了等于 0 的状况，起因是 0 并不代表任何 dom 元素，只是用来做占位的
      if (arrI !== 0) {j = result[result.length - 1]
        // 以后值大于子序列最初一项
        if (arr[j] < arrI) {
          // p 内存储以后值的前一位下标
          p[i] = j
          // 存储以后值的下标
          result.push(i)
          continue
        }
        u = 0
        v = result.length - 1
        // 以后数值小于子序列最初一项时，应用二分法找到第一个大于以后数值的下标
        while (u < v) {c = ((u + v) / 2) | 0
          if (arr[result] < arrI) {u = c + 1} else {v = c}
        }
        if (arrI < arr[result[u]]) {
          // 第一位不须要操作，一位它没有前一项
          if (u > 0) {
            // p 内存储找到的下标的前一位
            p[i] = result[u - 1]
          }
          // 找到下标，间接替换 result 中的数值
          result[u] = i
        }
      }
    }
    u = result.length
    v = result[u - 1]
    // 回溯，从最初一位开始，将 result 全副笼罩，while (u-- > 0) {result[u] = v
      v = p[v]
    }
    return result
  }

Vue3 DOM Diff 外围算法解析
wikipedia- 最长递增子序列

关于javascript:最长递增子序列及vue30中diff算法

求解最长递增子序列 leetcode300

动静布局：O(n²)

贪婪 + 二分查找：O(nlogn)

最长回升子序列进阶：失去正确的序列

vue3 DOM DIFF 算法

参考