从前置知识来看，最长递增子序列

什么是最长递增子序列

在一个给定数值的序列中。找到一个子序列，使得：

• 子序列的数值是依次增大的；
• 子序列的长度尽可能的长。

痛点：在实际业务中。列表渲染经常需要找出哪些节点可以复用而不必重新创建，LIS 正是底层算法的主要，一旦不了解，就会导致大量无效的 DOM 操作，引发卡顿。

贪心算法

该函数的实现主要是：贪心算法 + 二分法查找

. 贪心算法

贪心算法每一步只做当前最优选择。不回头，局部最优最终推出全局最优。老实说，

针对最长递增子序列的贪心策略：

• 一样长度的递增子序列。只保留末尾数字最小的一条。
• 末尾数字越小。后面越容易接上更大的数字，从而拼接出更长序列。

. 理解贪心优势

可能的长度为 2 的递增子序列有两条：

• （末尾：b)；
• （末尾：c)；如果 b 则保留第一条，因为它更有潜力继续增长。话说回来，

. 贪心两条处理逻辑

设 arrI = 当前遍历数字。result = 各长度最优末尾下标数组。

• If arr] 当前数字比现有最长序列末尾更大，可以直接拼接在后面序列长度 +1。其实，操作这方面，result.push。并记录前驱 P = result.
• If arr] ≥ arrI： 不能加长序列，但当前数字更小，有调整价值。使用二分法在 result 中找到第一个 ≥ arrI 的位置并替换下标。这样同长度的序列始终保留更小的末尾，以便后续

. 为什么贪心不能直接得到完整的 LIS

LIS 不仅要求数值递增。还要求下标严格递增。贪心只记录了每种长度的最小末尾，并未保存元素之间的先后链路。需要借助前驱数组 在遍历结束后回溯.

回溯

P 保存了以元素 a` 为时前一个元素的下标。遍历结束后从最长链条终点开始不断取前驱即可恢复完整 LIS。

let last = result;for {
result = last;last = P，}

LIS 的代码实现

function getSequence {
const p = arr.slice;说起来，// 前驱索引数组
const result =;按理说，// 贪心容器，存放下标
let i,j,u,v,c;const len = arr.length;for {
const arrI = arr;if {
j = result;if {
p = j，result.push;continue，}
// 二分查找第一个>= arrI 的位置
u = 0;v = result.length - 1;while {
c = >> 1;老实说，if u = c + 1;else v = c，}
if {
if p = result;result = i，}
}
}
// 回溯得到真实 LIS
let uIdx = result.length;let vIdx = result;while {
result = vIdx;vIdx = p，}
return result;}

Vue Diff 的整体流程

Pain Point：If you’re debugging a list update that seems to re‑render everything instead of just moving a few items。first place to look is high‑level flow inside #patchKeyedChildren.

function patchKeyedChildren(oldChildren,newChildren,container,parentAnchor) {
let i = 0;let oldEnd = oldChildren.length - 1;let newEnd = newChildren.length - 1;怎么说呢，// -------- 前序比较 --------
while { …}
// -------- 后序比较 --------
while { …}
// -------- 新节点> 老节点 --------
if { …}
// -------- 老节点> 新节点 --------
else if { …}
// -------- 中间乱序 Diff --------
else { …不过，}
}

至于前序比较。自前向后比较

while{
const oldVNode = oldChildren;const newVNode = normalizeVNode;
if){
patch，i++;}else break，}

至于后序比较，自后向前比较

while{
const oldVNode = oldChildren;const newVNode = normalizeVNode;if){
patch，oldEnd--;newEnd--，}else break;其实，}
至于**痛点**，如果这里漏掉了相同节点。会导致后面的乱序比对把本应复用的节点误判为删除/新增，从而产生多余渲染。

新节点> 老节点：挂载剩余新节点 

if{
const nextPos = newEnd +1;const anchor =
nextPoswhile{
const vnode= normalizeVNode;patch，i++;}


}


老节点> 新节点：卸载剩余老节点 

else if{
while{
unmount;i++，}
}


乱序 Diff 主要实现 

The most confusing part for many developers is “middle section” where Vue has to handle insertions、deletions、and moves simultaneously.

. 建立 “新节点 key → index” 映射表 

const keyToNewIndexMap=new Map;for{
const child=normalizeVNode;if{
keyToNewIndexMap.set;}
}


Pain Point：If you forget this map and fall back to `Array.findIndex`,diff complexity jumps from O to O。causing noticeable UI lag on large lists.


. 遍历旧节点、打补丁并记录位置映射 

let patched=0;const toBePatched=newEnd-newStartIndex+1;let moved=false;let maxNewIndexSoFar=0;老实说，const newIndexToOldIndexMap=
new Array.fill;for{
const prevChild=oldChildren;
if{
unmount;continue，}
let newIndex;if{
newIndex=keyToNewIndexMap.get;}else{
for{
if(newIndexToOldIndexMap===0 &&
isSameVNode){
newIndex=j;break，}
}
}
if{
unmount;}else{
// 填充映射表，用于后续 LIS 与挂载判断
newIndexToOldIndexMap=k+1;// 判断是否需要移动
if{
maxNewIndexSoFar=newIndex;}else{
moved=true;}
patch，patched++;不过，}



Pain Point：The “+1” offset in `k+1` acts as a sentinel value. Forgetting it makes “未匹配” 与 “真实索引为0”的情况混淆。从而导致错误卸载或重复挂载。说起来，


. maxNewIndexSoFar 的主要作用 

`maxNewIndexSoFar` 用来判断遍历过程中出现了“逆向”位置。即旧列表顺序在新列表里被打乱，需要进行移动操作。如果一直保持递增，则可以直接跳过 LIS 步骤，提高性能。

. 新旧索引地图 `newIndexToOldIndexMap` 的双重用途 


A. 判断“纯新增”：`newIndexToOldIndexMap === 0` 表示该新节点没有对应旧节点，需要执行挂载。

B. 为 LIS 提供数据源：`getSequence` 能够算出哪些已经在正确顺序上的节点可以免移动。


. 长度为 N 的数组求 LIS —— 最小化移动 

// 当需要移动时才计算 LIS
const increasingNewIndices =
moved?getSequence
: EMPTY_ARR;


Pain Point：If you always call `getSequence` even when `moved===false`。you waste CPU cycles on unnecessary binary searches.


. 从后往前遍历 `toBePatched`，执行挂载和移动 

let j=increasingNewIndices.length-1;for{
const nextIdx =newStartIdx+i;const nextChild =;
const anchor=
nextIdx+1



Pain Point：The condition `i!== increasingNewIndices` is easy to get wrong. A typo here will eir cause **all** nodes to be moved or **none**—both lead to visual glitches.



与实战建议 


**了解 L​IS**——它决定了哪些旧 DOM 可以原地复用，从而避免不必要的 DOM 移动。不过，

**建立 key→index 映射表**——省去 O 的搜索成本。是高性能 Diff 的关键一步。

*最大新索引* 用来快速判断是否真的需要进入耗时的 LIS 阶段。其实，

*新旧索引地图* 同时承担“新增检测”和“LIS 数据源”的双重职责。请务必保留 `+1` 哨兵值防止冲突。

*回溯* 与 *二分查找* 相结合，使得整个过程保持 O。在实际项目中，当你看到列表更新卡顿、DOM 重排频繁时请先检查这几块实现是否如上所述。否则很可能是因为遗漏了某个调整步骤导致性能倒退。