企业官网建设流程全解析

• 教程
• 文档
• 知识库

本文是「算法通关手册」AlgoNote 仓库中 LeetCode 0341「扁平化嵌套列表迭代器」的完整技术题解。文章以 docs/solutions/0300-0399/flatten-nested-list-iterator.md 为骨架，结合仓库中栈基础、二叉树非递归遍历等章节，深入讲解「惰性展开 + 栈」的迭代器设计思路。读完本文，你将掌握：如何用显式栈模拟递归遍历嵌套结构、next()与hasNext()如何协同做到按需展开，以及这一解法在仓库同类题目中的通用价值。

一、题目背景与核心问题

题目大意：给定一个嵌套的整数列表nestedList，列表中每个元素的类型都是NestedInteger。每个NestedInteger对象要么是一个整数，要么是一个列表；而列表中的元素又可能是整数或者其他列表。

要求：实现一个迭代器，将其扁平化，使之能够按照从左到右的顺序遍历出这个嵌套列表中的所有整数。

原文档给出了NestedInteger类需要提供的三个方法，这是解题的一切前提：

例如nestedList = [[1, 1], 2, [1, 1]]中，第一个元素是包含两个整数的嵌套列表，第二个元素是整数2，第三个元素又是一个嵌套列表。期望的遍历结果是[1, 1, 2, 1, 1]。

二、迭代器接口设计

需要实现的扁平化迭代器类NestedIterator包含三个成员：

• NestedIterator(List<NestedInteger> nestedList)：用嵌套列表nestedList初始化迭代器。
• int next()：返回嵌套列表的下一个整数。
• boolean hasNext()：如果仍然存在待迭代的整数，返回True；否则返回False。

注意接口约束：next()与hasNext()必须能按任意调用顺序协作，例如hasNext()可能被连续多次调用而不消费元素，也可能在next()之前被调用多次，因此next()必须保证返回的是「当前尚未消费的第一个整数」。

三、设计选择：惰性展开 vs 预展开

针对这类题目，有两种典型的实现策略：

策略一：预展开（eager flatten）。在构造函数里用递归（深度优先搜索）一次性把所有整数收集进一个线性列表，next()和hasNext()只是对列表索引的简单操作。优点是接口实现简单；缺点是初始化成本高，且空间上需要额外存储全部扁平化结果。仓库中 nested-list-weight-sum.md 展示的正是这种递归遍历NestedInteger的方式，可作为理解预展开的参考。

策略二：惰性展开（lazy expansion，即本题解采用的方式）。初始化时不对元素进行任何预处理，只在真正需要取数（即hasNext()被调用）时才逐层展开嵌套结构。这正是原文档解题思路的核心，其价值在于：

1. 零预处理成本：构造函数只有一次逆序入栈，时间复杂度为 $O(L)$（$L$ 为最外层元素个数）；
2. 按需计算：只有遇到列表时才会展开，未被访问的分支永远不会被展开；
3. 空间可控：不需要额外保存扁平化结果，栈中始终只保留「待处理边界」。

四、栈解法思路详解

由于栈具有**后进先出（LIFO）**的特性（参见仓库 03_01_stack_basic.md 对栈顶、栈底、入栈、出栈、查看栈顶的完整定义），而我们需要保证「从左到右」的输出顺序，因此入栈顺序与目标输出顺序相反。

初始化（构造函数）：

• 将nestedList中的所有元素逆序压入栈中。
• 即从最后一个元素开始，依次append到栈顶，这样栈顶元素就是原列表的第一个元素。

hasNext()的核心循环：

1. 当栈不为空时，查看栈顶元素cur：
   • 如果cur.isInteger()为True，说明栈顶就是一个待输出的整数，直接返回True；
   • 否则说明栈顶是一个嵌套列表，将其弹出，并把它的子元素逆序重新压入栈中（保证子元素从左到右排列），然后继续循环。
2. 如果栈变空，说明所有整数都已消费完毕，返回False。

next()：由于hasNext()已经保证栈顶是整数，next()只需弹出栈顶并调用getInteger()返回即可。

这种「用显式栈模拟递归展开」的手法，与仓库 05_02_binary_tree_traverse.md 中二叉树前序遍历的非递归实现完全同构：递归依赖系统调用栈，而这里用显式栈手动维护「待访问边界」，先压入右子树再压入左子树以保证遍历顺序。嵌套列表本质上就是一棵多叉树，NestedIterator就是这棵树的「前序遍历迭代器」。

五、完整代码

以下是原文档给出的完整 Python 实现（保留原文，不做删减）：

class NestedIterator: def __init__(self, nestedList: [NestedInteger]): self.stack = [] size = len(nestedList) for i in range(size - 1, -1, -1): self.stack.append(nestedList[i]) def next(self) -> int: cur = self.stack.pop() return cur.getInteger() def hasNext(self) -> bool: while self.stack: cur = self.stack[-1] if cur.isInteger(): return True self.stack.pop() for i in range(len(cur.getList()) - 1, -1, -1): self.stack.append(cur.getList()[i]) return False

六、代码逐行剖析与运行推演

构造函数__init__：self.stack = []初始化空栈；for i in range(size - 1, -1, -1)从最后一个元素往前遍历，逐个append。例如nestedList = [a, b, c]，入栈后栈内自底向上为c, b, a，栈顶是a，与期望的输出顺序一致。这与仓库 stack_sequential_stack.py 中「以列表作为存储、append入栈、末尾元素为栈顶」的顺序栈约定一致，只是这里不设容量上限，也不需要top指针——Python 列表天然支持动态扩容。

hasNext：cur = self.stack[-1]只查看栈顶而不弹出（即 peek 操作，参见仓库栈基础章节的「查看栈顶（Peek）」定义）。若栈顶是整数则直接返回True；若栈顶是列表，则self.stack.pop()弹出它，并将其子列表逆序压栈后继续循环。内层for i in range(len(cur.getList()) - 1, -1, -1)与构造函数中的逆序技巧完全一致。

next：因为调用next()之前通常都会先经过hasNext()的保证（栈顶必为整数），所以直接pop()并getInteger()即可。这也是 LeetCode 对该接口约定的一部分：next()只在存在下一个整数时被调用。

运行推演：设nestedList = [[1, 1], 2, [1, 1]]。

1. 构造：逆序入栈，栈（底→顶）为[[1,1], 2, [1,1]]（三个元素）。
2. 第一次hasNext()：栈顶是列表[1,1]，弹出并逆序压入1, 1，栈变为[[1,1], 2, 1, 1]；栈顶1是整数，返回True。
3. 第一次next()：弹出栈顶1，返回1。
4. 第二次hasNext()+next()：弹出栈顶1，返回1。
5. 第三次hasNext()：栈顶是整数2，返回True；next()弹出并返回2。
6. 第四次hasNext()：栈顶是列表[1,1]，展开压入两个1，返回True；next()返回1。
7. 第五次next()：返回最后一个1。
8. 第六次hasNext()：栈为空，返回False。

最终遍历顺序为1, 1, 2, 1, 1，完全符合预期。

七、复杂度分析

设嵌套列表中所有元素（整数与列表）的总数为 $N$，最大嵌套深度为 $D$：

• 时间复杂度：$O(N)$。构造阶段为 $O(L)$（$L$ 为最外层元素个数）；hasNext()与next()的均摊复杂度为 $O(1)$——每个嵌套列表在其被展开时弹出一次、其子元素各入栈一次，每个整数最终被弹出一次，所有元素累计只被处理常数次。
• 空间复杂度：$O(N)$。最坏情况下栈中同时存放全部元素，例如输入是一个元素个数很多的扁平列表或嵌套程度很深的链式结构。

相比预展开方案，惰性展开避免了「为根本不会被访问的分支付出代价」，在流式处理、超大嵌套输入等场景下优势明显。

八、与仓库相关内容的横向关联

本题涉及的NestedInteger接口、栈数据结构与 DFS 思想，在仓库中形成了一个完整的知识闭环，可以配套学习：

• 栈基础：本文栈操作（push/pop/peek）、LIFO 原则、顺序栈与链式栈实现均以此为理论基础；配套源码见 stack_sequential_stack.py。
• 0339. 嵌套列表加权和：同一NestedInteger接口的递归 DFS 解法，是「预展开 / 递归遍历」思路的对照版本。
• 0364. 嵌套列表加权和 II：同一接口的进阶变体，进一步体会深度维度上的处理差异。
• 0385. 迷你语法分析器：用栈解析嵌套列表的字符串表示、构造NestedInteger，与本题构成「解析 + 扁平化」的完整闭环——前者用栈「建树」，后者用栈「遍历树」。
• 二叉树的遍历：其「递归遍历 ↔ 显式栈非递归遍历」的转换手法，是理解本题惰性展开本质（把系统调用栈搬到显式栈）的最佳类比。

以上题目均收录于仓库 0300-0399 题解索引 中，可按序号顺序刷题。

九、面试与实战要点

1. 先想清楚hasNext()的职责：它不只是「判空」，还要负责「推进状态」——把栈顶的嵌套列表展开到栈顶变成整数为止。这是惰性迭代器与普通集合迭代器的最大区别。
2. 逆序入栈是核心技巧：栈顶必须始终指向「下一个应输出元素」，而NestedInteger列表是顺序存储的，二者方向相反，所以任何层级展开时都要逆序遍历。
3. 警惕getInteger()/getList()的误用：二者的调用前提是isInteger()的返回值，必须在调用前判断，否则会失败——这是NestedInteger接口约定的一部分（见原文档方法说明）。
4. 可扩展讨论：面试中可进一步讨论如何将该迭代器推广为「任意深度嵌套的通用扁平化工具」、如何支持remove()操作、以及惰性与预展开在时间与空间上的取舍。

结论：本题的「惰性展开 + 显式栈」方案，将树的递归遍历转化为迭代式遍历，是「设计迭代器」类题目的经典范式。掌握它，你就同时掌握了栈的逆序使用、hasNext()的状态推进语义，以及递归转非递归的核心手法。

• 教程
• 文档
• 知识库