算法面试真题补充：数据结构选型与解题模板

算法面试真题补充：数据结构选型与解题模板

本文根据编号 10《算法面试真题》、前端高频算法原题解析.pdf、第二篇 - 大厂面试手写题及算法、第四篇 - 面试高频踩坑解析 以及 高频真题解析与9月考点预测上/中/下 整理。资料中的重复题目只保留一处实现，其余位置提供题型索引、边界和交叉链接；课程、机构、报名信息和无法复核的效果数字已过滤。

1. 数据结构怎么分类和选型

可以先按元素之间的关系回答，再落到具体结构：

关系或目标	常用结构	典型操作/题型
连续、按下标访问	数组	随机访问、双指针、前缀和
先进后出	栈	括号匹配、单调栈、表达式求值
先进先出	队列	BFS、任务调度、滑动窗口
动态顺序连接	链表	频繁插入删除、LRU 节点移动
层次关系	树	递归、遍历、搜索、区间结构
多对多关系	图	连通性、最短路、拓扑排序
需要快速判重或映射	Set / Map	去重、频次统计、索引
需要维护最小/最大值	堆	Top K、优先队列、合并有序流

线性结构与非线性结构的区别，不在于“能不能用数组实现”，而在于元素之间的逻辑关系。队列可以用数组实现，树也可以用数组表示，但它们解决的问题和访问规则不同。选型时先写出需要的操作，再比较这些操作的时间和空间成本。（深入阅读：数据结构选型速记）

2. 复杂度回答的完整口径

时间复杂度描述输入规模 n 增大时，操作次数如何增长；空间复杂度描述额外使用的空间。面试时建议明确说明：

1. 是最坏、平均还是均摊复杂度；
2. 额外空间是否包含输入本身；
3. 递归栈、临时数组和缓存是否计入；
4. 是否存在最好情况的提前退出。

常见增长顺序为：

O(1) < O(log n) < O(n) < O(n log n) < O(n^2) < O(2^n) < O(n!)

几个容易误判的例子：（深入阅读：复杂度分析方法与陷阱）

• 连续的 O(n) 和 O(n^2) 取较高阶，整体为 O(n^2)，不是相加后保留常数。
• 两层独立循环通常是 O(n^2)；若内层每次把 i 翻倍，则可能是 O(n log n)。
• 动态数组尾部追加通常均摊 O(1)，扩容那一次可能是 O(n)。
• 递归算法要把“每层工作量”和“递归层数”同时写出来，不能只看递归调用次数。

3. Set、Map 与判重

JavaScript Set 使用基于 SameValueZero 的相等判断：重复的原始值只保留一份，NaN 可以被判定为同一个值；对象按引用判断，两个内容相同的对象仍是不同元素。

const values = new Set([1, 1, 2, NaN, NaN])
console.log([...values]) // [1, 2, NaN]

console.log(new Set([{ id: 1 }, { id: 1 }]).size) // 2

常见集合运算可以用 has 把查找降到均摊 O(1)：

const a = new Set([1, 2, 3])
const b = new Set([2, 3, 4])

const union = new Set([...a, ...b])
const intersection = new Set([...a].filter((value) => b.has(value)))
const difference = new Set([...a].filter((value) => !b.has(value)))

若题目需要“值到次数”的映射，使用 Map 或普通对象；若只需要判断是否出现过，Set 更直接。需要保留插入顺序时，不要把 Set 当作排序结构。（深入阅读：Set 与 Map 解题套路）

4. 树的遍历：递归、迭代和层序

前序、中序、后序的区别是访问根节点的时机：

前序：根 -> 左 -> 右
中序：左 -> 根 -> 右
后序：左 -> 右 -> 根

递归写法短，但深度很大的树可能触发调用栈限制。迭代前序要先压右子树再压左子树，才能保证左子树先出栈：

function preorder(root) {
  if (!root) return []
  const result = []
  const stack = [root]

  while (stack.length) {
    const node = stack.pop()
    result.push(node.val)
    if (node.right) stack.push(node.right)
    if (node.left) stack.push(node.left)
  }

  return result
}

层序遍历使用队列。不要在大型树上反复调用 shift()，因为移动数组元素可能带来额外的线性成本；用索引模拟队头更稳定：

function levelOrder(root) {
  if (!root) return []
  const result = []
  const queue = [root]
  let head = 0

  while (head < queue.length) {
    const levelEnd = queue.length
    const level = []

    while (head < levelEnd) {
      const node = queue[head++]
      level.push(node.val)
      if (node.left) queue.push(node.left)
      if (node.right) queue.push(node.right)
    }

    result.push(level)
  }

  return result
}

二叉搜索树的中序遍历有序，但普通 BST 在输入有序时会退化为链表。需要稳定的 O(log n) 查找时，应选择平衡树或其他有序索引，而不是只凭 BST 的平均复杂度作答。（深入阅读：树遍历模板、树的层序遍历）

5. 栈、队列与循环队列

栈适合表达“最近一次未完成的任务”，例如括号匹配、撤销和深度优先搜索。队列适合按到达顺序处理任务，例如广度优先搜索和限流队列。

固定容量循环队列要区分“空”和“满”。一种清晰实现是维护 head、tail 和 size，不要只依赖两个指针相等来猜状态：（深入阅读：括号匹配与表达式求值）

class CircularQueue {
  constructor(capacity) {
    this.data = new Array(capacity)
    this.capacity = capacity
    this.head = 0
    this.tail = 0
    this.size = 0
  }

  enqueue(value) {
    if (this.size === this.capacity) return false
    this.data[this.tail] = value
    this.tail = (this.tail + 1) % this.capacity
    this.size += 1
    return true
  }

  dequeue() {
    if (this.size === 0) return undefined
    const value = this.data[this.head]
    this.head = (this.head + 1) % this.capacity
    this.size -= 1
    return value
  }
}

6. 链表与 LRU：为什么需要双向链表

单链表插入和删除的关键是保存相邻节点的引用。若已经拿到前驱节点，插入或删除本身是 O(1)；按位置查找节点仍需 O(n) 遍历。

LRU（Least Recently Used）缓存要求：

• get(key) 读取后把节点移动到“最近使用”端；
• put(key, value) 更新或插入后也移动到最近端；
• 超出容量时删除最久未使用端；
• 两类操作都尽量为 O(1)。

因此通常组合 Map + 双向链表：Map 负责按 key 找节点，双向链表负责 O(1) 摘除和插入。（深入阅读：双向链表与 LRU Cache）

class LRUCache {
  constructor(capacity) {
    this.capacity = Math.max(0, capacity)
    this.map = new Map()
    this.head = { next: null, prev: null }
    this.tail = { next: null, prev: null }
    this.head.next = this.tail
    this.tail.prev = this.head
  }

  remove(node) {
    node.prev.next = node.next
    node.next.prev = node.prev
  }

  insertAfterHead(node) {
    node.next = this.head.next
    node.prev = this.head
    this.head.next.prev = node
    this.head.next = node
  }

  get(key) {
    const node = this.map.get(key)
    if (!node) return -1
    this.remove(node)
    this.insertAfterHead(node)
    return node.value
  }

  put(key, value) {
    if (this.capacity === 0) return

    let node = this.map.get(key)
    if (node) {
      node.value = value
      this.remove(node)
    } else {
      node = { key, value, prev: null, next: null }
      this.map.set(key, node)
    }

    this.insertAfterHead(node)
    if (this.map.size > this.capacity) {
      const oldest = this.tail.prev
      this.remove(oldest)
      this.map.delete(oldest.key)
    }
  }
}

面试中要说明哨兵节点的作用：它们消除了头尾插入、删除时的分支，让链表操作更容易保持一致。

7. 堆与 Top K

二叉堆是满足堆序性质的完全二叉树，常用数组存储：

parent(i) = floor((i - 1) / 2)
left(i)   = 2 * i + 1
right(i)  = 2 * i + 2

小顶堆的根是当前最小值，大顶堆的根是当前最大值。插入或删除根节点后向上或向下调整，复杂度为 O(log n)；查看根节点是 O(1)。

求数组中最大的 k 个数时，可以维护容量为 k 的小顶堆：

1. 先把前 k 个元素放入堆；
2. 后续元素若大于堆顶，替换堆顶并下沉；
3. 最终堆中保留最大的 k 个元素。

复杂度为 O(n log k)，当 k 远小于 n 时比完整排序的 O(n log n) 更合适。回答优先队列题时要先说明“优先级最高的元素是最小还是最大”，避免堆方向写反。（深入阅读：TopK 小顶堆实战）

8. 图：邻接表、邻接矩阵与访问标记

邻接矩阵查询一条边是否存在很快，但空间为 O(V^2)；邻接表只保存实际存在的边，空间约为 O(V + E)，更适合稀疏图。无向边需要在两个方向各记录一次，有向边只记录出边方向。

DFS 可以递归或显式使用栈，BFS 使用队列。访问标记应在“入队”时完成，而不是出队时才标记，否则同一节点可能被重复加入队列：

function bfs(graph, start) {
  const visited = new Set([start])
  const queue = [start]
  let head = 0
  const order = []

  while (head < queue.length) {
    const node = queue[head++]
    order.push(node)

    for (const next of graph[node] || []) {
      if (visited.has(next)) continue
      visited.add(next)
      queue.push(next)
    }
  }

  return order
}

无权图的最短边数通常用 BFS；需要判断所有连通分量时，要从每个尚未访问的节点重新启动遍历。图题的复杂度应写成 O(V + E)，不要只写 O(n) 而忽略边数。（深入阅读：无权图最短路径、图的 DFS 连通性）

9. 排序怎么比较

面试回答排序算法，除了时间复杂度，还应说明稳定性、额外空间和是否原地：（深入阅读：快排与归并排序对比）

算法	平均时间	额外空间	稳定性	适合场景
冒泡	O(n^2)	O(1)	稳定	教学、小规模且接近有序
插入	O(n^2)	O(1)	稳定	小规模或局部有序
选择	O(n^2)	O(1)	通常不稳定	写入次数需要较少
快排	平均 O(n log n)	递归栈	通常不稳定	通用内存内排序
归并	O(n log n)	O(n)	稳定	稳定排序、外部排序

9.1 冒泡排序的提前退出

如果一轮扫描没有发生交换，说明数组已经有序，可以提前结束。记录最后一次交换位置还可以缩小下一轮边界，避免重复比较已排好区域。

9.2 快速排序的风险

每次选择最大或最小元素作为枢轴，会把分区退化成 0 + (n - 1)，最坏为 O(n^2)。随机枢轴、三数取中和尾递归优化可以降低退化概率，但不能把最坏复杂度口头说成永远是 O(n log n)。

9.3 归并排序与分治

归并排序先把问题拆成两个规模约为 n/2 的子问题，再在线性时间内合并，递推式为 T(n) = 2T(n/2) + O(n)，因此为 O(n log n)。它的稳定性来自合并时相等元素优先取左侧元素。

10. 二分查找的边界模型

写二分前先确定区间是闭区间 [left, right] 还是半开区间 [left, right)，并让初始化、循环条件和收缩方式保持一致。查找“第一个满足条件的位置”时，命中后不要立即返回，而是记录答案并继续收缩左侧：

function lowerBound(nums, target) {
  let left = 0
  let right = nums.length // 半开区间

  while (left < right) {
    const mid = left + Math.floor((right - left) / 2)
    if (nums[mid] >= target) right = mid
    else left = mid + 1
  }

  return left
}

旋转有序数组二分还要先判断哪一半有序，再判断目标是否落在该半区间；数组含大量重复值时，nums[left] === nums[mid] === nums[right] 会丢失方向信息，通常需要收缩一端并接受最坏 O(n)。（深入阅读：查找边界模型、答案二分）

11. 分治、动态规划、贪心和回溯的区别

四种思想都可能出现递归，但依赖关系不同：

思想	核心条件	典型题
分治	子问题相互独立，解完再合并	归并排序、快排
动态规划	子问题重叠且具有最优子结构	爬楼梯、背包、最长子序列
贪心	每一步选当前最优，且选择可安全延续	区间调度、跳跃游戏
回溯	在选择空间中搜索，失败后撤销选择	全排列、组合、N 皇后

动态规划的一般步骤是：定义状态含义，写出转移，确定初始值和遍历顺序，再分析是否能压缩空间。分治不会因为“用了递归”就自动成为动态规划；如果子问题重复计算，应考虑记忆化或自底向上 DP。

贪心必须说明为什么局部选择不会破坏全局最优，不能只凭几个样例成立。回溯则要明确“路径、选择列表、结束条件”，去重通常需要排序后跳过同层重复元素，或使用 used 集合记录已选项。（深入阅读：动态规划五步分析法、区间贪心、回溯模板）

12. 扁平节点与树结构互转

搭建器、菜单和权限题常给出扁平节点：每个节点带 id 和 parentId，要求转换成树。不要用“每插入一个节点就向整棵树查找父节点”的写法；先建索引，再连接父子关系，才能稳定做到 O(n)。完整的重复 ID、孤儿节点、环和遍历实现见扁平数据与树结构互转。

function listToTree(list) {
  const nodes = new Map()
  const roots = []

  for (const item of list) {
    if (nodes.has(item.id)) throw new Error(`duplicate id: ${item.id}`)
    nodes.set(item.id, { ...item, children: [] })
  }

  for (const node of nodes.values()) {
    if (node.parentId == null) {
      roots.push(node)
      continue
    }

    const parent = nodes.get(node.parentId)
    if (!parent) throw new Error(`missing parent: ${node.parentId}`)
    parent.children.push(node)
  }

  return roots
}

function treeToList(roots) {
  const result = []
  const stack = roots.slice().reverse().map((node) => ({ node, parentId: null }))

  while (stack.length) {
    const { node, parentId } = stack.pop()
    const { children = [], ...record } = node
    result.push({ ...record, parentId })
    for (let index = children.length - 1; index >= 0; index -= 1) {
      stack.push({ node: children[index], parentId: node.id })
    }
  }

  return result
}

两遍建树的时间复杂度是 O(n)，索引和输出树占用 O(n) 空间；递归 DFS 的额外空间是 O(h)，深度不可信时可以像上面一样使用显式栈。生产数据还要校验环、重复 ID、孤儿节点和最大深度，不能只保证“能渲染”。

13. 受限并发的 Promise Scheduler

并发调度题的关键不是把 Promise.all 再包一层，而是明确“任务何时启动、失败是否影响其他任务、结果顺序和取消语义”。下面的最小实现限制同时运行的任务数，并保持结果和输入顺序一致：

function runWithConcurrency(taskFactories, limit) {
  if (!Number.isInteger(limit) || limit < 1) {
    return Promise.reject(new RangeError('limit must be a positive integer'))
  }

  const results = new Array(taskFactories.length)
  let nextIndex = 0
  let active = 0
  let settled = 0
  let failed = false

  return new Promise((resolve, reject) => {
    const launch = () => {
      if (failed) return
      if (settled === taskFactories.length) {
        resolve(results)
        return
      }

      while (active < limit && nextIndex < taskFactories.length) {
        const index = nextIndex++
        active += 1
        Promise.resolve()
          .then(() => taskFactories[index]())
          .then((value) => {
            results[index] = value
            settled += 1
          })
          .catch((error) => {
            failed = true
            reject(error)
          })
          .finally(() => {
            active -= 1
            if (!failed && settled !== taskFactories.length) launch()
          })
      }
    }

    if (taskFactories.length === 0) resolve([])
    else launch()
  })
}

这个版本采用“首个失败即 reject”的策略；如果业务需要尽可能完成全部任务，应改为记录每项的 fulfilled/rejected 状态，不能悄悄吞掉异常。进一步追问包括：队列上限、优先级、公平性、AbortSignal、单任务超时、只对幂等请求重试，以及排队时长和执行时长的指标。可运行的 worker 池、取消和可测试红绿灯实现见异步调度专题。

14. 循环异步任务：以红绿灯为例

需要无限循环执行异步步骤时，使用 while 配合 await 比递归回调更容易停止和测试。停止信号应在等待前后都检查：

function wait(ms, signal) {
  return new Promise((resolve, reject) => {
    let settled = false
    let timer
    const onAbort = () => finish(reject, new DOMException('Aborted', 'AbortError'))
    const cleanup = () => {
      clearTimeout(timer)
      signal?.removeEventListener('abort', onAbort)
    }
    const finish = (settle, value) => {
      if (settled) return
      settled = true
      cleanup()
      settle(value)
    }

    timer = setTimeout(() => finish(resolve), ms)
    if (!signal) return
    if (signal.aborted) {
      onAbort()
      return
    }
    signal.addEventListener('abort', onAbort, { once: true })
  })
}

async function runTrafficLight(phases, signal) {
  if (!Array.isArray(phases) || phases.length === 0) {
    throw new RangeError('at least one phase is required')
  }
  if (!signal) throw new TypeError('an AbortSignal is required')

  while (!signal.aborted) {
    for (const phase of phases) {
      if (signal.aborted) return
      await phase.run()
      await wait(phase.duration, signal)
    }
  }
}

面试时要说明：循环任务必须有退出条件；组件卸载、页面隐藏或请求取消时要 abort；计时器和事件监听器要清理，避免后台页面持续占用资源。具体的阶段状态、不变量和 AbortSignal 清理见异步调度专题。

15. 高频字符串和链表手写题

15.1 链表相交按引用判断

“相交”表示两个链表在某个节点对象之后共享同一条尾链，不是节点值相同。双指针走完各自链表后切换到另一条链表头部，两个指针会在 O(m + n) 时间、O(1) 额外空间内相遇：

function getIntersectionNode(headA, headB) {
  let left = headA
  let right = headB

  while (left !== right) {
    left = left ? left.next : headB
    right = right ? right.next : headA
  }

  return left
}

15.2 字符串相加和单词反转

大数相加从末位向前推进，并把进位保留在循环条件中，避免转成 JavaScript Number 后丢失精度；完整的输入规范化、乘法扩展和边界见大数运算专题：

function addStrings(a, b) {
  let i = a.length - 1
  let j = b.length - 1
  let carry = 0
  const chars = []

  while (i >= 0 || j >= 0 || carry) {
    const sum = Number(a[i--] || 0) + Number(b[j--] || 0) + carry
    chars.push(String(sum % 10))
    carry = Math.floor(sum / 10)
  }

  return chars.reverse().join('')
}

翻转单词时先定义空白规则。若只需处理普通空格，trim().split(/\s+/).reverse().join(' ') 足够；若输入可能很大或需要保留流式处理，应逐字符扫描并从后向前输出，避免额外的多次拷贝。不要把“按字符反转”误当作“按单词反转”。

15.3 最小栈

用一个栈保存值、另一个栈保存“截至当前位置的最小值”，push、pop、getMin 都是 O(1)。重复最小值也要重复压入，否则弹出一个最小值后无法恢复下一个相同最小值：

class MinStack {
  constructor() {
    this.values = []
    this.mins = []
  }

  push(value) {
    this.values.push(value)
    const current = this.mins.length
      ? Math.min(value, this.mins[this.mins.length - 1])
      : value
    this.mins.push(current)
  }

  pop() {
    if (!this.values.length) return undefined
    this.mins.pop()
    return this.values.pop()
  }

  getMin() {
    return this.mins[this.mins.length - 1]
  }
}

15.4 链表求和与字符串乘法

链表求和先确认数位方向：逆序链表从头到尾相加，正序链表要用栈对齐低位。循环条件必须包含最后一次进位，结果是否新建节点、是否恢复输入结构也属于函数契约。（完整实现：链表加法：进位与方向）

字符串乘法不能直接转成 Number 或依赖未约定的大数库。竖式乘法把 num1[i] * num2[j] 累加到结果数组的对应位置，再从低位统一处理进位，时间 O(mn)、结果空间 O(m+n)。输入为 "0" 时应立即返回 "0"，并移除结果前导零；已有大数加法专题中的 BigNumber 示例可作为实现参考，但不要把它误称为任意精度小数库。（相关：大数相加）

15.5 三数和、矩阵搜索与有序合并

最接近三数之和先复制并排序，固定一个下标后用对撞指针；和小于目标时增大左指针，和大于目标时减小右指针，命中目标可提前结束。复杂度为 O(n^2)（含排序），不能在未证明单调性时随意跳过组合。

行列均递增的二维矩阵可从左下角搜索：大于目标上移，小于目标右移，每步排除一行或一列，复杂度 O(rows + columns)。若只保证每行有序，必须改用逐行二分。

有序数组原地合并时从尾部向前写，避免覆盖第一个数组中尚未读取的元素；题目若没有预留空间，返回新数组是另一种契约。（完整实现和边界：排序双指针：三数之和与顺序匹配）

15.6 子序列、字典词与回文

判断子序列用同向指针扫描长串，空的候选串应返回 true；“子序列”允许跳过字符，“子串”不允许。固定长串、查询很多时，可预处理每个字符的位置表并二分查找下一位置，但要说明预处理内存成本。

删除字符匹配字典题先验证候选词是子序列，再按长度降序、字典序升序比较；不能只按输入顺序返回第一个匹配词。候选遍历的复杂度还要计入候选词展开和比较，约为 O(D * S + L)。回文题则先定义可比较字符和大小写规则，ASCII 题可在两端跳过非字母数字并原地对撞；需要 Unicode 用户感知字符时应采用明确的规范化和分词策略。（完整实现：排序双指针：三数之和与顺序匹配）

15.7 饼干匹配与贪心证明

把胃口和饼干尺寸升序排列，用当前最小可行饼干满足最小胃口。饼干太小就跳过，因为它也无法满足后面更大的胃口；匹配成功则两个指针都前进。排序后复杂度为 O(c log c + s log s)。这份贪心只最大化满足人数；若改成收益、优先级或公平性目标，必须重新给出交换论证或改用其他模型。（完整实现：排序双指针：三数之和与顺序匹配）

15.8 字符窗口：异位词与最小覆盖

异位词是固定长度窗口，维护目标频次和窗口频次；最小覆盖是可变窗口，右边界扩张到覆盖目标后持续收缩左边界。用“频次刚好满足的字符种类数”维护 matchedKinds/formed，不要只比较 Map.size，否则目标含重复字符时会误判。每个位置最多进出窗口一次；按 code point 展开字符串时，连同展开数组和计数表计为 O(n+m+k)，不计结果输出。（完整实现：字符覆盖：异位词与最小覆盖子串）

以上题型的统一检查顺序是：先确认输入是否有序、是否允许修改、字符/节点身份规则和空值契约；再写指针不变量；最后用重复值、连续进位、无答案和边界窗口做最小对拍。这样可以避免把 PDF 中的示例代码或复杂度口径直接当成通用结论。

16. N 数之和：先选模型再优化

如果题目要求从 n 个数中选出恰好 k 个且总和为 target，回溯模板更容易处理重复值、剪枝和任意 n。位掩码枚举适合 n 很小的教学题，但 JavaScript 的位运算受 32 位有符号整数限制，不能无条件写成 1 << n：

function chooseSum(nums, k, target) {
  const values = [...nums].sort((a, b) => a - b)
  const result = []
  const path = []

  function dfs(start, remaining, sum) {
    if (remaining === 0) {
      if (sum === target) result.push([...path])
      return
    }
    if (values.length - start < remaining) return

    for (let i = start; i <= values.length - remaining; i += 1) {
      if (i > start && values[i] === values[i - 1]) continue
      path.push(values[i])
      dfs(i + 1, remaining - 1, sum + values[i])
      path.pop()
    }
  }

  dfs(0, k, 0)
  return result
}

需要去重时先排序；若数组允许负数，不能仅凭“当前和已经超过目标”剪枝。复杂度取决于剪枝效果，最坏接近 O(2^n)，空间主要是递归深度和结果集。（来源：25年上半年中大厂高频面试总结(下).pdf 第 27-31 页、25年下半年面试真题预测.pdf 第 26-39 页。）

17. 版本号与数组合并

17.1 版本号比较

先确认版本规则：普通数字段比较和 SemVer（预发布标识、构建元数据）不是同一道题。若只比较由点分隔的数字段，应按段转成安全的整数语义，不能直接用字符串比较，也不要把超长段强制转成 Number：

function compareNumericVersions(left, right) {
  const a = left.split('.')
  const b = right.split('.')
  const length = Math.max(a.length, b.length)

  for (let i = 0; i < length; i += 1) {
    const x = (a[i] ?? '0').replace(/^0+(?=\d)/, '')
    const y = (b[i] ?? '0').replace(/^0+(?=\d)/, '')
    if (x.length !== y.length) return x.length > y.length ? 1 : -1
    if (x !== y) return x > y ? 1 : -1
  }

  return 0
}

这个实现把 1.0 和 1.0.0 视为相等，并能比较超过 JavaScript 安全整数范围的数字段。若题目要求完整 SemVer，应另外处理 -alpha.1 的预发布优先级和 +build 元数据，不能把上面的函数冒充完整规范解析器。

17.2 合并两个有序数组

若输入数组已经有序，双指针可以在线性时间内合并；若要求原地合并且第一个数组尾部有空位，应从后向前写，避免覆盖尚未读取的元素：

function mergeSortedArrays(left, right) {
  const result = []
  let i = 0
  let j = 0

  while (i < left.length || j < right.length) {
    if (j === right.length || (i < left.length && left[i] <= right[j])) {
      result.push(left[i++])
    } else {
      result.push(right[j++])
    }
  }

  return result
}

复杂度是 O(m + n) 时间和 O(m + n) 结果空间；如果题目实际问的是“合并重叠区间”，先按起点排序，再维护当前区间的最大右端点，不能把两种“合并数组”混为一谈。（来源：25年上半年中大厂高频面试总结(下).pdf 第 31 页。）

面试答题顺序

面对陌生算法题，可以按以下顺序组织答案：

1. 先确认输入规模、是否有序、是否允许修改输入和返回格式。
2. 选择数据结构，说明它能把哪一个操作降到目标复杂度。
3. 写不变量或状态定义，再写主循环/递归。
4. 用边界样例验证：空输入、单元素、重复值、最坏顺序和容量上限。
5. 最后给出时间复杂度、额外空间和可替代方案。

这样既能覆盖 PDF 中的基础实现题，也能接住“为什么这样选”“最坏情况是什么”和“如何优化”的追问。

本轮资料专题入口

为避免把同一道题复制到多个位置，下面按来源和主题给出可直接深入的入口：

资料中的题型	详细专题	重点边界
JSON 转树、树转 JSON、前序/中序/后序	扁平数据与树结构互转	父节点乱序、重复 ID、孤儿节点、环、深树栈溢出
无重复递增随机数组、数组去重	数组去重与不重复随机数组	[0, max] 端点、均匀抽样、对象键、稳定顺序
红绿灯、受限并发 Promise	异步调度：红绿灯与受限并发	惰性启动、并发上限、首错/全量、取消和计时器清理
模拟大数相加	大数运算：字符串加法与乘法	前导零、连续进位、安全整数、乘法下标
滑动窗口最大值	单调队列：滑动窗口最大值	过期下标、重复最大值、shift() 退化
小镇法官	小镇法官：入度与出度	N = 1、自环、重复关系、度数差证明
爬楼梯、最小花费、最大子数组	线性 DP：爬楼梯、最小花费与打家劫舍	楼顶位置、空/全负输入、状态压缩

来源清单：前端高频算法原题解析.pdf、高频真题解析与9月考点预测上.pdf、高频真题解析与9月考点预测中.pdf、高频真题解析与9月考点预测下.pdf。预测下主要是模块、性能和浏览器原理题，未发现需要另建算法实现的独立题型；相关内容应分别阅读对应工程化和前端三大件专题。