Vue3（domdiff）最长递归子序列求解简易版（超简单）

⚠️ 关键词（每一个都需要理解）

• 动态规划（O(N^2)）（不提倡）
• 贪心 + 二分法 （O(N * logN)）(✅)
• vue3 patch 阶段 domdiff 最复杂的情况（数组与数组）
• 索引值 （结果返回的是下标）
• 前驱节点追溯解决序列不对（重点）

js 代码实现

var lengthOfLIS = function (nums) {let result = [0];let p = nums.slice(); // 缓存每一个result的前置节点let len = nums.length;for (let i = 0; i < len; i++) {let j = result[result.length - 1];let x = nums[j];if (nums[i] > x) {p[i] = j;result.push(i);} else {// 二分查找 （不懂好好研究一下）let b = result.length;let a = 0;while (a < b) {c = (a + b) >> 1;if (nums[result[c]] >= nums[i]) {b = c;} else {a = c + 1;}}p[i] = result[a - 1];result[a] = i;}}// 前驱节点追溯解决序列不对let u = result.length;let v = result[u - 1];while (u-- > 0) {result[u] = v;v = p[v];// 这就是为什么p存前置节点，为了回溯}return result;
};

写完感想

• 代码写的很粗糙，但是核心思想大差不差
• 自己多思考，多写几遍就会掌握
• 推荐看一看《Vue.js技术内幕》

欢迎关注