LeetCode 341. 扁平化嵌套列表迭代器

2026-04-02 HGNULB 约 8 分钟

文章信息 8 个分类 6 个标签

分类

题目描述

✅ 341. 扁平化嵌套列表迭代器

题意分析

给定一个嵌套结构：它是一个列表，其中每个元素要么是一个整数，要么又是一个同样结构的列表，嵌套深度不限。要实现迭代器接口 next 与 hasNext，把所有整数按照它们在原结构中从左到右出现的顺序逐个吐出来。

接口形状是最强的约束信号。题目没有要求「返回一个数组」，而是要求实现迭代器，说明设计上期望的是按需产出：调用方可能只取前几个元素就停下，也可能反复调用 hasNext 而不调用 next。这两种调用模式都必须正确。

可用的操作被限死在三个方法上：判断当前节点是不是整数、取出整数值、取出子列表。没有「取父节点」也没有「取长度」以外的导航能力，所以遍历状态必须自己维护。

边界比想象中多。空的顶层列表要让 hasNext 直接返回 false；形如「只包含若干空列表」的输入（如 [[], [[]]]）里一个整数都没有，hasNext 同样必须返回 false，而这需要连续剥掉好几层才能确定；嵌套可以很深，纯递归实现存在爆栈风险。

解法：栈模拟

核心思路

最直接的做法是在构造函数里递归地做一次深度优先遍历，把所有整数摊进一个数组，next 就是按下标往后走。这样写最短，也确实能通过。

它的问题在于把全部代价提前付清了：即使调用方只想取第一个整数，构造函数也已经把整棵嵌套树走完，并为所有整数分配了空间。对于「迭代器」这个抽象来说，这违背了惰性求值的初衷；而且递归深度等于嵌套深度，输入足够深时会栈溢出。

换个角度观察：递归遍历之所以能保持正确顺序，靠的是调用栈记住了「当前节点之后还有哪些兄弟没处理」。而 next 是一次次被外部调用的，函数调用栈在两次调用之间根本不存在，所以只能把这份状态搬到一个显式的栈里自己保管。

栈里保存的是「已知存在但尚未消费」的节点。因为栈是后进先出，要让最左边的元素最先出来，压栈时必须从后往前。真正需要取值时，如果栈顶是个列表，就把它弹掉并把它的子元素同样逆序压回去，重复这个过程直到栈顶是整数或栈被清空。

关键的设计决策是把这套整理逻辑全部放进 hasNext，让 next 退化成一次纯粹的弹出。由此得到的不变量是：每当 hasNext 返回 true，栈顶一定是一个整数，且栈中从顶到底恰好是剩余未消费元素按正确顺序排列的结果；每当 hasNext 返回 false，栈一定为空。这个不变量同时保证了 hasNext 的幂等性——栈顶已是整数时它不做任何修改，连续调用多少次结果都一样。

解题步骤

构造迭代器时，从后往前遍历顶层列表并逐个压栈。逆序是为了抵消栈的后进先出：最先要产出的元素必须最后压入，才能位于栈顶。

hasNext 进入一个循环，只要栈非空就检查栈顶。用循环而不是单次判断，是因为一次调用可能需要连续剥掉多层嵌套（例如栈顶是一个只含空列表的列表）。

若栈顶是整数，立刻返回 true 且不改动栈。这一步保证了幂等：外部连续调用两次 hasNext 不会消耗掉任何元素。

若栈顶是列表，先把它弹出，再把它的子元素从后往前压回栈中，然后继续下一轮检查。必须先弹后压，否则这个列表会永远留在栈里被反复展开，直接死循环。

栈被清空仍未遇到整数时返回 false。这正是「全是空列表」这类输入的正确出口。

next 直接弹出栈顶并取出整数值。它建立在「调用前已经调过 hasNext」这一迭代器通用约定之上，因此不需要再做任何整理。

以 [[1, 1], 2, [1, 1]] 走一遍：构造时从后往前压入，栈从顶到底是 [1,1]、2、[1,1]。第一次 hasNext：栈顶是列表，弹出它，把子元素 1、1 逆序压回，栈变成 1、1、2、[1,1]；再次检查，栈顶是整数，返回 true。next 弹出并返回 1，栈剩 1、2、[1,1]。第二次 hasNext 栈顶已是整数，直接 true，next 返回 1，栈剩 2、[1,1]。第三次同理，next 返回 2，栈剩 [1,1]。第四次 hasNext：栈顶是列表，弹出并逆序压回两个 1，栈变成 1、1，返回 true；next 返回 1，再一次 next 返回 1，栈空。最后一次 hasNext 发现栈空，返回 false。整体输出 1、1、2、1、1，与原始顺序一致。

代码实现

public class NestedIterator implements Iterator<Integer> {
    private final Deque<NestedInteger> stack = new ArrayDeque<>();

    public NestedIterator(List<NestedInteger> nestedList) {
        for (int i = nestedList.size() - 1; i >= 0; i--) {
            stack.push(nestedList.get(i));
        }
    }

    @Override
    public Integer next() {
        return stack.pop().getInteger();
    }

    @Override
    public boolean hasNext() {
        // hasNext 负责把栈顶列表展开到栈顶为整数。
        while (!stack.isEmpty()) {
            NestedInteger top = stack.peek();
            if (top.isInteger()) {
                return true;
            }

            stack.pop();
            List<NestedInteger> list = top.getList();
            for (int i = list.size() - 1; i >= 0; i--) {
                stack.push(list.get(i));
            }
        }
        return false;
    }
}

type NestedIterator struct {
    // 为了保持原始顺序，向栈中放入列表元素时必须从后往前压入。
    stack []*NestedInteger
}

func Constructor(nestedList []*NestedInteger) *NestedIterator {
    stack := make([]*NestedInteger, 0, len(nestedList))
    for i := len(nestedList) - 1; i >= 0; i-- {
        stack = append(stack, nestedList[i])
    }
    return &NestedIterator{stack: stack}
}

func (it *NestedIterator) Next() int {
    n := it.stack[len(it.stack)-1]
    it.stack = it.stack[:len(it.stack)-1]
    return n.GetInteger()
}

func (it *NestedIterator) HasNext() bool {
    for len(it.stack) > 0 {
        top := it.stack[len(it.stack)-1]
        if top.IsInteger() {
            return true
        }

        it.stack = it.stack[:len(it.stack)-1]
        list := top.GetList()
        for i := len(list) - 1; i >= 0; i-- {
            it.stack = append(it.stack, list[i])
        }
    }
    return false
}

复杂度分析

时间复杂度：构造函数 $O(k)$，其中 $k$ 是顶层元素个数，只压栈不展开；next 是 $O(1)$；hasNext 均摊 $O(1)$——每个节点在整个迭代生命周期里至多入栈一次、出栈一次，因此完整遍历一遍的总代价是 $O(N)$，$N$ 为嵌套结构中的节点总数。

空间复杂度：$O(N)$，最坏情况下（例如所有整数都挂在同一个子列表里）一次展开就会把它们全部压入栈中。相比构造时递归摊平的写法，本实现的优势不在最坏空间，而在于不受嵌套深度限制、且未被消费的部分不必提前展开。

关键点总结

迭代器类题目的通用套路是「把递归的隐式状态显式化」。函数调用栈在两次 next 之间不复存在，能跨调用保留的只有对象字段，所以必须自己维护一个栈。

栈是后进先出，凡是要用栈保持原始顺序，压入时就必须逆序。这一条在前序遍历、嵌套展开、括号处理里反复出现，值得当成肌肉记忆。

职责划分要干净：让 hasNext 独占所有展开与整理工作，next 只做弹出。把展开塞进 next 会导致 hasNext 无法判断真实状态，而两边都做又会重复展开。

展开必须写成循环而非单次判断，因为空列表可以层层套叠，一次调用可能要连续剥掉多层才能确定答案。

面试视角：面试官大概率会问「为什么不在构造时直接摊平」。答案要落在两点上——惰性产出让提前终止的场景省下大量工作，以及显式栈不受嵌套深度限制而递归会爆栈；同时坦白最坏情况下两者空间同阶，展现出的判断力比背下代码更重要。

面试视角：另一个常见追问是「hasNext 修改了内部状态，算不算副作用」。可以答：这是惰性迭代器的标准设计，只要保证幂等即可；本实现在栈顶已是整数时直接返回、不改动栈，因此连续调用结果一致。

易错点总结

错误写法：构造时按下标从前往后压栈。用例 [1, 2] → 压入 1 再压入 2，栈顶是 2，输出 2、1，正确顺序是 1、2。

错误写法：展开子列表时按正序压回。用例 [[1, 2]] → 弹出外层列表后先压 1 再压 2，栈顶变成 2，输出 2、1，正确顺序是 1、2。

错误写法：hasNext 里只剥一层就返回，用 if 代替 while。用例 [[[]], 1] → 弹出 [[]] 压回一个空列表后就返回 true，随后 next 对着一个列表调用取整数值，抛异常或返回垃圾值。

错误写法：hasNext 看到栈顶是列表时直接压子元素，忘了先把这个列表弹出。用例 [[1]] → 该列表永远留在栈底之上被反复展开，栈无限增长，死循环。

错误写法：把展开逻辑放进 next，hasNext 只判断栈是否为空。用例 [[], []] → 栈非空使 hasNext 返回 true，next 展开后发现无整数可弹，在空栈上出栈抛异常，正确行为是 hasNext 返回 false。

错误写法：hasNext 在栈顶已是整数时也执行弹出再压回的整理动作。用例外部连续调用两次 hasNext → 幂等性被破坏，栈内容在无消费的情况下被改动，后续顺序出错。

错误写法：构造函数对空的顶层列表不做处理，hasNext 上来就取栈顶再判断。用例 [] → 在空栈上取顶元素抛异常，正确行为是返回 false。

错误写法：改用递归在构造时摊平，且不考虑深度。用例嵌套深度上万的输入 → 递归调用栈溢出；显式栈写法把深度转移到堆上，不受此限制。

相似题目

题目	难度	考察点
173. 二叉搜索树迭代器	中等	同样用显式栈把递归改成按需产出，但展开方向固定为一路向左
430. 扁平化多级双向链表	中等	要求一次性就地展开并维护前驱指针，不是惰性迭代
394. 字符串解码	中等	嵌套在右括号处归约，栈里要同时保存倍数与已拼接的前缀
224. 基本计算器	困难	栈保存的是括号外的运算上下文与符号，展开时机由括号闭合触发