diff 算法

约 5346 字大约 18 分钟

2026-03-29

在子节点更新中，如果新旧子节点都是数组，最简单的做法是先把旧子节点全部卸载，再把新子节点全部挂载

oldVNode.children.forEach((child) => unmount(child));
newVNode.children.forEach((child) => patch(null, child, container));

这当然能得到正确结果，但代价很高。因为很多时候新旧两组子节点只是内容变化、顺序变化，或者局部新增删除，并不需要把所有真实 DOM 都销毁再重建。如果节点数量较少，性能差异可能不明显，但如果节点数量较多，这种 "全量替换" 的方式就会导致明显的性能问题。Diff 算法就是为了解决这个问题而设计的

重要

Diff 算法要解决的问题就是：在保证最终 DOM 顺序正确的前提下，尽可能复用旧节点对应的真实 DOM，并减少移动、挂载和卸载操作

Key 的作用

如果两个节点的 type 不同，一般可以直接认为不是同一个节点。但如果一组子节点都是同一种标签，比如都是 p，仅靠 type 就无法判断它们之间的对应关系

const oldChildren = [
  { type: 'p', children: '1' },
  { type: 'p', children: '2' },
  { type: 'p', children: '3' },
];

const newChildren = [
  { type: 'p', children: '3' },
  { type: 'p', children: '1' },
  { type: 'p', children: '2' },
];

上面这组节点里，所有节点的 type 都是 p。如果没有额外标识，渲染器无法知道新的第一个 p 到底对应旧的哪一个 p。所以需要引入 key

const oldChildren = [
  { type: 'p', key: 1, children: '1' },
  { type: 'p', key: 2, children: '2' },
  { type: 'p', key: 3, children: '3' },
];

const newChildren = [
  { type: 'p', key: 3, children: '3' },
  { type: 'p', key: 1, children: '1' },
  { type: 'p', key: 2, children: '2' },
];

有了 key 之后，渲染器就可以判断：

新节点 key: 3 对应旧节点 key: 3
新节点 key: 1 对应旧节点 key: 1
新节点 key: 2 对应旧节点 key: 2

这时更新就不再是 "按位置替换"，而是可以进入 "按身份复用"。这也是 keyed diff 的基础

Diff

简单 Diff

简单 Diff 将更动作拆成三个基本动作：

找到可复用节点并调用 patch
新节点在旧节点中不存在时挂载
旧节点在新节点中不存在时卸载

先处理相同位置的节点

如果新旧两组子节点长度相同，而且顺序也没有变化，那么可以直接按索引逐个 patch

思路

先取新旧两组子节点的公共长度 commonLength，公共部分逐个更新。新列表更长时，多出来的部分挂载；旧列表更长时，多出来的部分卸载

代码

function patchKeyedChildren(oldChildren, newChildren, container) {
  const oldLen = oldChildren.length;
  const newLen = newChildren.length;
  const commonLength = Math.min(oldLen, newLen);

  for (let i = 0; i < commonLength; i++) {
    patch(oldChildren[i], newChildren[i], container);
  }

  if (newLen > oldLen) {
    for (let i = commonLength; i < newLen; i++) {
      patch(null, newChildren[i], container);
    }
  } else if (oldLen > newLen) {
    for (let i = commonLength; i < oldLen; i++) {
      unmount(oldChildren[i]);
    }
  }
}

通过 key 找到可复用节点

只按索引更新有一个问题：一旦顺序发生变化，就会把本来可以复用的节点当成不同节点处理

思路

遍历新子节点，再到旧子节点中寻找相同 key 的节点。只要找到了，就说明这两个虚拟节点对应同一个真实 DOM，可以调用 patch 更新

代码

function patchKeyedChildren(oldChildren, newChildren, container) {
  for (let i = 0; i < newChildren.length; i++) {
    const newVNode = newChildren[i];

    for (let j = 0; j < oldChildren.length; j++) {
      const oldVNode = oldChildren[j];

      if (newVNode.key === oldVNode.key) {
        patch(oldVNode, newVNode, container);
        break;
      }
    }
  }
}

判断节点是否需要移动

找到可复用节点之后，还要判断它对应的真实 DOM 是否需要移动

这里有一个关键点：新子节点的顺序，就是最终真实 DOM 应该呈现的顺序。遍历新子节点时，如果在旧子节点中找到的索引不是递增的，就说明当前节点需要移动

思路

用 lastIndex 记录遍历过程中遇到的最大旧索引。如果当前找到的旧索引 j 小于 lastIndex，说明这个节点在旧列表中的位置靠前，但在新列表中被放到了后面，此时需要移动

代码

function patchKeyedChildren(oldChildren, newChildren, container) {
  let lastIndex = 0;

  for (let i = 0; i < newChildren.length; i++) {
    const newVNode = newChildren[i];

    for (let j = 0; j < oldChildren.length; j++) {
      const oldVNode = oldChildren[j];

      if (newVNode.key === oldVNode.key) {
        patch(oldVNode, newVNode, container);

        if (j < lastIndex) {
          const prevVNode = newChildren[i - 1];

          if (prevVNode) {
            const anchor = prevVNode.el.nextSibling;
            insert(newVNode.el, container, anchor);
          }
        } else {
          lastIndex = j;
        }

        break;
      }
    }
  }
}

处理新增节点
如果新节点在旧节点中找不到相同 key，说明它是新增节点，需要挂载
思路
新节点的插入位置由它前一个新节点决定。如果前一个新节点存在，就把当前节点插入到前一个节点真实 DOM 的下一个兄弟节点前面；如果前一个新节点不存在，说明它是第一个节点，锚点就是容器的第一个子节点
代码
```
if (!matched) {
  const prevVNode = newChildren[i - 1];
  let anchor = null;

  if (prevVNode) {
    anchor = prevVNode.el.nextSibling;
  } else {
    anchor = container.firstChild;
  }

  patch(null, newVNode, container, anchor);
}
```
处理需要卸载的旧节点
遍历新节点只能发现哪些新节点需要更新或挂载，但无法发现哪些旧节点已经不存在
思路
更新完成后，再遍历旧子节点。只要某个旧节点的 key 在新子节点中不存在，就说明它应该被卸载
代码
```
for (let i = 0; i < oldChildren.length; i++) {
  const oldVNode = oldChildren[i];
  const has = newChildren.find((newVNode) => newVNode.key === oldVNode.key);

  if (!has) {
    unmount(oldVNode);
  }
}
```
简单 Diff 的问题
简单 Diff 可以复用 DOM，也可以处理新增、删除和移动。但它判断移动的方式比较粗糙，容易产生不必要的移动
例如旧序列是 [1, 2, 3]，新序列是 [3, 1, 2]。简单 Diff 会认为 1 和 2 都需要移动，但更优的做法其实是只把 3 移动到最前面
这就是双端 Diff 要解决的问题

双端 Diff

双端 Diff 的核心是：同时从新旧两组子节点的两端开始比较

这样做的原因是，真实场景中节点移动经常发生在头尾附近。如果只从左到右扫描，很容易错过更少移动次数的方案；而双端比较可以更快发现 "旧头到新尾"、"旧尾到新头" 这类移动

准备四个端点

思路

分别用四个索引指向旧列表头部、旧列表尾部、新列表头部、新列表尾部。每轮循环只处理这四个端点中的匹配情况

代码

let oldStartIdx = 0;
let oldEndIdx = oldChildren.length - 1;
let newStartIdx = 0;
let newEndIdx = newChildren.length - 1;

let oldStartVNode = oldChildren[oldStartIdx];
let oldEndVNode = oldChildren[oldEndIdx];
let newStartVNode = newChildren[newStartIdx];
let newEndVNode = newChildren[newEndIdx];

旧头和新头比较

如果旧头和新头的 key 相同，说明这个节点本来就在头部，不需要移动，只需要更新，然后两个头部索引同时向后移动

if (oldStartVNode.key === newStartVNode.key) {
  patch(oldStartVNode, newStartVNode, container);

  oldStartVNode = oldChildren[++oldStartIdx];
  newStartVNode = newChildren[++newStartIdx];
}

旧尾和新尾比较

如果旧尾和新尾的 key 相同，说明这个节点本来就在尾部，也不需要移动，只需要更新，然后两个尾部索引同时向前移动

else if (oldEndVNode.key === newEndVNode.key) {
  patch(oldEndVNode, newEndVNode, container);

  oldEndVNode = oldChildren[--oldEndIdx];
  newEndVNode = newChildren[--newEndIdx];
}

旧头和新尾比较

如果旧头和新尾相同，说明旧头节点在新列表中移动到了尾部。更新后，需要把旧头对应的真实 DOM 移动到当前旧尾的后面

else if (oldStartVNode.key === newEndVNode.key) {
  patch(oldStartVNode, newEndVNode, container);
  insert(oldStartVNode.el, container, oldEndVNode.el.nextSibling);

  oldStartVNode = oldChildren[++oldStartIdx];
  newEndVNode = newChildren[--newEndIdx];
}

旧尾和新头比较

如果旧尾和新头相同，说明旧尾节点在新列表中移动到了头部。更新后，需要把旧尾对应的真实 DOM 移动到当前旧头的前面

else if (oldEndVNode.key === newStartVNode.key) {
  patch(oldEndVNode, newStartVNode, container);
  insert(oldEndVNode.el, container, oldStartVNode.el);

  oldEndVNode = oldChildren[--oldEndIdx];
  newStartVNode = newChildren[++newStartIdx];
}

四个端点都没有命中

如果四种端点比较都没有命中，就退回到旧列表中查找新头节点

思路

如果找到了，就说明该旧节点可以复用，先 patch，再把它移动到旧头前面，并把旧数组当前位置置为 undefined，避免后续重复处理。如果找不到，说明新头是新增节点，直接挂载到旧头前面

代码

else {
  const indexInOld = oldChildren.findIndex(
    (node) => node && node.key === newStartVNode.key,
  );

  if (indexInOld > 0) {
    const vnodeToMove = oldChildren[indexInOld];
    patch(vnodeToMove, newStartVNode, container);
    insert(vnodeToMove.el, container, oldStartVNode.el);
    oldChildren[indexInOld] = undefined;
  } else {
    patch(null, newStartVNode, container, oldStartVNode.el);
  }

  newStartVNode = newChildren[++newStartIdx];
}

循环结束后的补充处理
双端循环结束后，还可能剩余新节点或旧节点
思路
如果旧节点先处理完，新列表中剩下的节点就是新增节点；如果新节点先处理完，旧列表中剩下的节点就是需要卸载的节点
代码
```
if (oldEndIdx < oldStartIdx && newStartIdx <= newEndIdx) {
  for (let i = newStartIdx; i <= newEndIdx; i++) {
    patch(null, newChildren[i], container, oldStartVNode?.el ?? null);
  }
} else if (newEndIdx < newStartIdx && oldStartIdx <= oldEndIdx) {
  for (let i = oldStartIdx; i <= oldEndIdx; i++) {
    if (oldChildren[i]) {
      unmount(oldChildren[i]);
    }
  }
}
```
双端 Diff 的问题
双端 Diff 相比简单 Diff，已经能减少不少不必要的移动。但它仍然有一个明显问题：端点比较失败后，仍然需要在旧列表里查找节点
更重要的是，它不能很好地识别中间区域中 "相对顺序没有变化" 的节点。比如某些节点虽然整体位置发生了偏移，但它们之间的相对顺序仍然稳定，这些节点其实不需要移动
快速 Diff 会通过预处理和最长递增子序列来处理这个问题

快速 Diff

Vue 3 中的 keyed children 更新，核心思想更接近快速 Diff：

先从头部处理相同的前置节点
再从尾部处理相同的后置节点
如果剩余部分只是新增，直接挂载
如果剩余部分只是删除，直接卸载
如果剩余部分既有新增、删除，也有移动，就进入复杂区间处理
复杂区间中，用索引表定位可复用节点，用最长递增子序列减少 DOM 移动

预处理相同的前置节点

前置节点指新旧两组子节点从头部开始连续相同的部分。这部分节点在最终顺序中位置不变，只需要更新，不需要移动

let j = 0;
let oldVNode = oldChildren[j];
let newVNode = newChildren[j];

while (oldVNode.key === newVNode.key) {
  patch(oldVNode, newVNode, container);
  j++;
  oldVNode = oldChildren[j];
  newVNode = newChildren[j];
}

预处理相同的后置节点

后置节点指新旧两组子节点从尾部开始连续相同的部分。这部分同样只需要更新，不需要移动

let oldEnd = oldChildren.length - 1;
let newEnd = newChildren.length - 1;

oldVNode = oldChildren[oldEnd];
newVNode = newChildren[newEnd];

while (oldVNode.key === newVNode.key) {
  patch(oldVNode, newVNode, container);
  oldEnd--;
  newEnd--;
  oldVNode = oldChildren[oldEnd];
  newVNode = newChildren[newEnd];
}

简单情况：只需要新增
如果旧列表已经处理完，但新列表中还有未处理节点，说明剩下的都是新增节点
思路
新增节点要插入到正确位置。锚点可以通过 newEnd + 1 找到，如果后面还有节点，就插到它前面；如果后面没有节点，就插入到末尾
```
if (j > oldEnd && j <= newEnd) {
  const anchorIndex = newEnd + 1;
  const anchor = anchorIndex < newChildren.length
    ? newChildren[anchorIndex].el
    : null;

  while (j <= newEnd) {
    patch(null, newChildren[j++], container, anchor);
  }
}
```
简单情况：只需要卸载
如果新列表已经处理完，但旧列表中还有未处理节点，说明剩下的都是需要卸载的旧节点
```
else if (j > newEnd && j <= oldEnd) {
  while (j <= oldEnd) {
    unmount(oldChildren[j++]);
  }
}
```
复杂区间：建立新节点索引表
如果前面两个简单分支都不满足，说明剩余区间中同时存在复用、移动、新增或卸载
思路
先把新子节点剩余区间的 key -> index 做成索引表。这样遍历旧子节点时，就可以用 key 快速判断它是否还存在于新列表中
代码
```
const oldStart = j;
const newStart = j;
const count = newEnd - newStart + 1;
const source = new Array(count).fill(-1);

const keyIndex = new Map();

for (let i = newStart; i <= newEnd; i++) {
  keyIndex.set(newChildren[i].key, i);
}
```
复杂区间：填充 source
source 数组用来记录新子节点剩余区间中的每个节点，在旧子节点中的位置
```
for (let i = oldStart; i <= oldEnd; i++) {
  const oldVNode = oldChildren[i];
  const k = keyIndex.get(oldVNode.key);

  if (k !== undefined) {
    const newVNode = newChildren[k];
    patch(oldVNode, newVNode, container);
    source[k - newStart] = i;
  } else {
    unmount(oldVNode);
  }
}
```
如何理解 source
如果 source[i] 是 -1，说明新列表中的这个节点在旧列表中不存在，需要挂载
如果 source[i] 不是 -1，它的值就是该节点在旧列表中的位置。这个位置序列可以用来判断哪些节点需要移动
判断是否需要移动
遍历旧节点并填充 source 时，可以顺手判断新索引是否递增
思路
用 pos 记录遍历过程中遇到的最大新索引。如果后续遇到的 k 小于 pos，说明顺序发生了倒退，需要移动
```
let moved = false;
let pos = 0;

if (k < pos) {
  moved = true;
} else {
  pos = k;
}
```
使用最长递增子序列减少移动
最长递增子序列（Longest Increasing Subsequence，LIS），它解决的问题是：从一个数组里，找出一组保持原有先后顺序、并且数值递增的最长序列
什么是子序列
子序列不是子数组。子数组必须连续，子序列不要求连续，但顺序不能乱
例如：
```
原数组： [2, 1, 5, 3, 6, 4, 8, 9, 7]

子序列： [2, 5, 6, 8] 或 [1, 3, 4, 9] 等等
```
它们不一定连续，但在原数组里的相对顺序没有变
什么是递增
递增就是后一个数比前一个数大
例如：
```
[1, 3, 4, 8, 9]  是递增的
[1, 5, 3, 6]     不是递增的，因为 3 < 5
```
什么是最长
在所有递增子序列里，长度最长的那个，就是最长递增子序列
例如：
```
[2, 1, 5, 3, 6, 4, 8, 9, 7]

它的最长递增子序列可以是：
[1, 3, 4, 8, 9]
[2, 3, 4, 8, 9]
```
Diff 当中使用最长递增子序列是用于判断哪些节点可以不移动
```
旧节点顺序：
A B C D

新节点顺序：
B C A D
```
先把节点映射成它们在旧节点中的位置
```
新节点：B C A D
旧索引: 1 2 0 3
```
所以得到数组: [1, 2, 0, 3] 找这个数组的最长递增子序列是 [1, 2, 3]，对应的节点是 B C D，它们在新旧列表中的相对顺序没有变，可以保持不动；而 A 不在最长递增子序列里，说明它需要移动
思路
从后往前遍历新子节点剩余区间。如果当前位置是 -1，说明是新增节点，挂载；如果当前位置不在最长递增子序列里，说明需要移动；如果在最长递增子序列里，说明可以保持原位
代码
```
if (moved) {
  const seq = getSequence(source);
  let s = seq.length - 1;

  for (let i = count - 1; i >= 0; i--) {
    const pos = i + newStart;
    const newVNode = newChildren[pos];
    const nextPos = pos + 1;
    const anchor = nextPos < newChildren.length
      ? newChildren[nextPos].el
      : null;

    if (source[i] === -1) {
      patch(null, newVNode, container, anchor);
    } else if (i !== seq[s]) {
      insert(newVNode.el, container, anchor);
    } else {
      s--;
    }
  }
}
```

本质说明

Diff 算法就在说一件事：当一组子节点从旧状态变为新状态时，怎么用最少的 DOM 操作，把页面更新成新状态

比如旧的是：

A B C

新的变成

C A B

最笨的做法就是删掉 A B C，然后再重新创建 C A B 这可定可以实现，但代价很大。Diff 想做的是：发现了 A B C 都还在，只是顺序变了，所以根本不需要删掉重建，只需只移动 DOM

重要

所以最核心的问题只有三个:

哪些节点可以复用
哪些节点是新增的
哪些节点需要删除或移动

这个就是 key 的作用，没有 key 时，Vue 只能猜：旧的第 1 个节点对应新的第 1 个节点。有了 key Vue 就可以确定旧的 key: 3 对应新的 key: 3。所以 Diff 本质上就不是在比较 DOM，而是比较两组虚拟节点的身份和顺序

简单 Diff 说的是：先遍历新节点，然后去旧的节点里找有没有相同的 key，如果找到了就复用节点 patch 一下；如果没找到就说明是新节点，需要挂载；最后在反过来检查旧节点，如果旧节点的 key 在新节点里找不到，说明它被删除了，需要卸载。这种 Diff 的问题是：它没有利用新旧两组节点的顺序信息，导致很多不必要的移动

然后就是双端 Diff，在 Vue2 中主要使用的双端 Diff。双端 Diff 说的是：先从两端开始比较，它每次只比较四种情况

新头 vs 旧头
新尾 vs 旧尾
新头 vs 旧尾
新尾 vs 旧头

因为很多移动都是发生在头尾附近的，比如

旧: A B C
新: C A B

那么简单 Diff 可能会移动 A 和 B，而双端 Diff 就能发现 C 在旧列表的尾部，直接把 C 移到头部就好了。但双端 Diff 的问题是：如果四种情况都没有命中，它就只能退回到旧列表里查找新头节点，这时就没什么优化了

最后就是快速 Diff，在 Vue3 中使用的是双端 Diff。快速 Diff 说的是：先预处理两端相同的节点，剩下的就是中间区间了

旧: A B C D E
新: A B X D E

这个时候头和尾都没有变化，A B 是相同前缀，D E 是相同后缀，真正需要处理的只有中间，所以快速 Diff 的第一步就是跳过相同的头，在跳过相同的尾，只处理不同的部分，如果中间只是新增，则挂载；只是删除，则卸载；如果既有新增、删除、移动就进入复杂处理。这个时候就可以通过索引表快速定位可复用节点，并用最长递增子序列来减少移动次数

先把新子节点剩余区间的 key -> index 做成 Map 索引表。这样遍历旧子节点时，就可以用 key 快速判断它是否还存在于新列表中

现阶段完整代码

快速 Diff 的核心结构

src

renderer.ts

sequence.ts

src/renderer.ts
import { getSequence } from './sequence';

function createRenderer(options) {
  const {
    insert,
    setElementText,
  } = options;

  function render(vnode, container) {
    if (vnode) {
      patch(container._vnode, vnode, container);
    } else if (container._vnode) {
      unmount(container._vnode);
    }

    container._vnode = vnode;
  }

  function patch(oldVNode, newVNode, container, anchor = null) {
    if (oldVNode && oldVNode.type !== newVNode.type) {
      unmount(oldVNode);
      oldVNode = null;
    }

    if (!oldVNode) {
      mountElement(newVNode, container, anchor);
    } else {
      patchElement(oldVNode, newVNode);
    }
  }

  function patchElement(oldVNode, newVNode) {
    const el = newVNode.el = oldVNode.el;

    patchProps(oldVNode, newVNode, el);
    patchChildren(oldVNode, newVNode, el);
  }

  function patchChildren(oldVNode, newVNode, container) {
    const oldChildren = oldVNode.children;
    const newChildren = newVNode.children;

    if (typeof newChildren === 'string') {
      if (Array.isArray(oldChildren)) {
        oldChildren.forEach((child) => unmount(child));
      }

      setElementText(container, newChildren);
    } else if (Array.isArray(newChildren)) {
      if (Array.isArray(oldChildren)) {
        patchKeyedChildren(oldChildren, newChildren, container);
      } else {
        setElementText(container, '');
        newChildren.forEach((child) => patch(null, child, container));
      }
    } else {
      if (Array.isArray(oldChildren)) {
        oldChildren.forEach((child) => unmount(child));
      } else if (typeof oldChildren === 'string') {
        setElementText(container, '');
      }
    }
  }

  function patchKeyedChildren(oldChildren, newChildren, container) {
    let j = 0;
    let oldVNode = oldChildren[j];
    let newVNode = newChildren[j];

    while (
      oldVNode &&
      newVNode &&
      oldVNode.key === newVNode.key
    ) {
      patch(oldVNode, newVNode, container);
      j++;
      oldVNode = oldChildren[j];
      newVNode = newChildren[j];
    }

    let oldEnd = oldChildren.length - 1;
    let newEnd = newChildren.length - 1;

    oldVNode = oldChildren[oldEnd];
    newVNode = newChildren[newEnd];

    while (
      oldVNode &&
      newVNode &&
      oldVNode.key === newVNode.key
    ) {
      patch(oldVNode, newVNode, container);
      oldEnd--;
      newEnd--;
      oldVNode = oldChildren[oldEnd];
      newVNode = newChildren[newEnd];
    }

    if (j > oldEnd && j <= newEnd) {
      const anchorIndex = newEnd + 1;
      const anchor = anchorIndex < newChildren.length
        ? newChildren[anchorIndex].el
        : null;

      while (j <= newEnd) {
        patch(null, newChildren[j++], container, anchor);
      }
    } else if (j > newEnd && j <= oldEnd) {
      while (j <= oldEnd) {
        unmount(oldChildren[j++]);
      }
    } else {
      const oldStart = j;
      const newStart = j;
      const count = newEnd - newStart + 1;
      const source = new Array(count).fill(-1);
      const keyIndex = new Map();

      let moved = false;
      let pos = 0;
      let patched = 0;

      for (let i = newStart; i <= newEnd; i++) {
        keyIndex.set(newChildren[i].key, i);
      }

      for (let i = oldStart; i <= oldEnd; i++) {
        const oldVNode = oldChildren[i];

        if (patched >= count) {
          unmount(oldVNode);
          continue;
        }

        const k = keyIndex.get(oldVNode.key);

        if (k !== undefined) {
          const newVNode = newChildren[k];

          patch(oldVNode, newVNode, container);
          patched++;
          source[k - newStart] = i;

          if (k < pos) {
            moved = true;
          } else {
            pos = k;
          }
        } else {
          unmount(oldVNode);
        }
      }

      const seq = moved ? getSequence(source) : [];
      let s = seq.length - 1;

      for (let i = count - 1; i >= 0; i--) {
        const pos = i + newStart;
        const newVNode = newChildren[pos];
        const nextPos = pos + 1;
        const anchor = nextPos < newChildren.length
          ? newChildren[nextPos].el
          : null;

        if (source[i] === -1) {
          patch(null, newVNode, container, anchor);
        } else if (moved) {
          if (i !== seq[s]) {
            insert(newVNode.el, container, anchor);
          } else {
            s--;
          }
        }
      }
    }
  }

  function mountElement(vnode, container, anchor = null) {
    // 挂载元素逻辑在前文已经实现
  }

  function patchProps(oldVNode, newVNode, el) {
    // 更新 props 逻辑在前文已经实现
  }

  function unmount(vnode) {
    const parent = vnode.el.parentNode;

    if (parent) {
      parent.removeChild(vnode.el);
    }
  }

  return {
    patch,
    render,
  };
}
src/sequence.ts
export function getSequence(source: number[]): number[] {
  const length = source.length;
  const dp = new Array(length).fill(1);
  const prev = new Array(length).fill(-1);
  let maxIndex = -1;

  for (let i = 0; i < length; i++) {
    if (source[i] === -1) {
      dp[i] = 0;
      continue;
    }

    for (let j = 0; j < i; j++) {
      if (
        source[j] !== -1 &&
        source[j] < source[i] &&
        dp[j] + 1 > dp[i]
      ) {
        dp[i] = dp[j] + 1;
        prev[i] = j;
      }
    }

    if (maxIndex === -1 || dp[i] > dp[maxIndex]) {
      maxIndex = i;
    }
  }

  const result: number[] = [];
  let current = maxIndex;

  while (current !== -1) {
    result.unshift(current);
    current = prev[current];
  }

  return result;
}

补充篇

原理篇

工程化搭建

响应式

渲染器

渲染器的基础实现

基础篇

原理篇