如何手写数组扁平化 flat？

简化版

数组扁平化是把嵌套数组展开到指定深度。递归时遍历当前数组：若元素仍是数组且深度大于 0，就递归处理；否则放入结果。flat() 默认展开 1 层，flat(Infinity) 才是完全展开。原生 flat 还会跳过被展开层级中的空槽。

详细版

基础实现如下：

function flat(input, depth = 1) {
  const result = []

  function visit(array, remaining) {
    for (let i = 0; i < array.length; i++) {
      if (!(i in array)) continue
      const value = array[i]
      if (Array.isArray(value) && remaining > 0) {
        visit(value, remaining - 1)
      } else {
        result.push(value)
      }
    }
  }

  visit(input, depth)
  return result
}

flat([1, [2, [3]]]) 得到 [1, 2, [3]]，传入 2 才得到 [1, 2, 3]。时间复杂度约为 O(n)，其中 n 是实际访问的元素数；结果数组需要 O(n) 额外空间，递归还会占用与嵌套深度相关的调用栈。

完整版教学

一、先把题目合同说清楚

面试官说“手写 flat”时，第一件事不是立刻写递归，而是确认需要做到哪一层。

维度	常见教学要求	原生 `Array.prototype.flat` 的行为
默认深度	通常约定为 1	默认就是 1
完全展开	接受 `Infinity`	支持 `Infinity`
稀疏数组	容易误读成 `undefined`	跳过被访问层级中的空槽
可展开对象	常只处理数组	方法本身是泛型，但只有真正的数组会被展开

例如 [1, , [2, , 3]].flat() 的结果是 [1, 2, 3]，空槽不会被追加为 undefined。但 [1, [2, , [3]]].flat(1) 中更深层数组没有继续展开，它内部的空槽仍保留在那个嵌套数组里。

面试中可以先完成“数组输入 + 非负深度”的主体，再主动说明深度规范化、稀疏数组和超深递归的边界，这比声称几行代码完全等价于原生实现更准确。

二、递归实现的关键细节

下面实现覆盖常见面试合同，并显式跳过空槽：

function normalizeDepth(depth) {
  const number = Number(depth)
  if (Number.isNaN(number) || number <= 0) return 0
  if (number === Infinity) return Infinity
  return Math.floor(number)
}

function flatRecursive(input, depth = 1) {
  if (!Array.isArray(input)) throw new TypeError('input must be an array')

  const result = []
  const maxDepth = normalizeDepth(depth)

  function visit(array, remaining) {
    for (let index = 0; index < array.length; index++) {
      if (!(index in array)) continue
      const value = array[index]
      if (Array.isArray(value) && remaining > 0) {
        visit(value, remaining === Infinity ? Infinity : remaining - 1)
      } else {
        result.push(value)
      }
    }
  }

  visit(input, maxDepth)
  return result
}

index in array 用来区分“空槽”和“值恰好是 undefined 的元素”。前者不进入结果，后者必须保留。Infinity - 1 仍是 Infinity，代码中特判主要是为了让意图更直观。

三、用例要覆盖真正的边界

只测 [1, [2, 3]] 无法证明实现正确，至少要覆盖下面几组：

flatRecursive([1, [2, [3]]])            // [1, 2, [3]]
flatRecursive([1, [2, [3]]], 2)         // [1, 2, 3]
flatRecursive([1, [2, [3]]], 0)         // [1, [2, [3]]]
flatRecursive([1, [2, [3]]], Infinity)  // [1, 2, 3]
flatRecursive([1, , undefined])          // [1, undefined]
flatRecursive([1, { 0: 2, length: 1 }]) // 对象原样保留

数字示例也能说明“深度”的含义：对于四层结构 [[[[1]]]]，传 depth = 2 只移除外侧两层，结果仍是 [[1]]，而不是 [1]。

四、迭代写法如何保证顺序

嵌套深度可能达到几万层时，递归实现可能触发调用栈上限。可以把待处理项放进显式栈，但后进先出的栈必须倒序入栈：

function flatIterative(input, depth = 1) {
  if (!Array.isArray(input)) throw new TypeError('input must be an array')

  const result = []
  const stack = []
  const maxDepth = normalizeDepth(depth)

  for (let i = input.length - 1; i >= 0; i--) {
    if (i in input) stack.push([input[i], maxDepth])
  }

  while (stack.length > 0) {
    const [value, remaining] = stack.pop()
    if (Array.isArray(value) && remaining > 0) {
      const next = remaining === Infinity ? Infinity : remaining - 1
      for (let i = value.length - 1; i >= 0; i--) {
        if (i in value) stack.push([value[i], next])
      }
    } else {
      result.push(value)
    }
  }

  return result
}

迭代版避免了 JavaScript 调用栈溢出，但显式栈仍然占内存；它不是“零空间”方案。

五、复杂度要按实际访问量解释

设算法实际访问的数组槽位数为 n，嵌套最大深度为 h：

实现	时间复杂度	结果之外的辅助空间	主要风险
递归	O(n)	O(h) 调用栈	h 太大时栈溢出
显式栈	O(n)	最坏 O(n)	宽数组会让工作栈变大

输出数组本身还需要 O(m) 空间，m 是最终元素数。把 result.push(...child) 用在超大数组上，也可能因为一次函数调用传入过多参数而报错，所以逐项追加更稳妥。

六、原生语义与教学实现的边界

真正的原生 flat 还包含对象转换、长度读取、深度转换、派生数组创建等规范步骤。它能读取类数组，但只递归展开真正的数组：

const arrayLike = { length: 2, 0: [1, 2], 1: 3 }
Array.prototype.flat.call(arrayLike) // [[1, 2], 3]

因此，本文函数故意把输入限定为数组。若面试官要求 polyfill，还应讨论数组子类、Symbol.species、属性访问器的副作用，以及接近数组最大索引时的处理，不能把常规递归版称为规范级 polyfill。

七、常见误区与追问

误区：flat() 默认会完全展开。 默认深度是 1，完全展开需要显式传入 Infinity。
误区：空槽等价于值为 undefined。 空槽没有对应属性，应被跳过；显式的 undefined 是真实元素，必须进入结果。
误区：迭代实现天然保持原顺序。 使用后进先出栈时要倒序压入子元素，否则结果会反转。
追问：为什么不用 reduce 加 concat？ 可以写，但多次创建和复制中间数组，数据量大时通常不如复用一个结果数组直接追加。
追问：如何避免极深嵌套导致爆栈？ 改用显式栈或生成器，把递归状态放到堆内存中管理。
追问：对象里有 length 和数字键会被递归展开吗？ 原生方法能遍历类数组，但只有真正的数组元素才会继续展开。
追问：复杂度为什么不简单写成 O(顶层数组长度)？ 顶层长度不包含嵌套工作量，应按所有实际访问的槽位计算。

八、加强记忆

合同：默认深度 1，Infinity 才完全展开。
递归：数组且剩余深度大于 0 才继续下钻。
空槽：用 index in array 区分空槽和 undefined。
顺序：显式栈必须倒序入栈，出栈结果才保持原顺序。
边界：递归版怕深度，迭代版也要付出显式栈空间。
表述：常见手写题实现的是核心语义，不应冒充完整 ECMAScript polyfill。

简化版

详细版