教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本文是「算法通关手册」AlgoNote 仓库中 LeetCode 0341「扁平化嵌套列表迭代器」的完整技术题解。文章以 docs/solutions/0300-0399/flatten-nested-list-iterator.md 为骨架结合仓库中栈基础、二叉树非递归遍历等章节深入讲解「惰性展开 栈」的迭代器设计思路。读完本文你将掌握如何用显式栈模拟递归遍历嵌套结构、next()与hasNext()如何协同做到按需展开以及这一解法在仓库同类题目中的通用价值。一、题目背景与核心问题题目大意给定一个嵌套的整数列表nestedList列表中每个元素的类型都是NestedInteger。每个NestedInteger对象要么是一个整数要么是一个列表而列表中的元素又可能是整数或者其他列表。要求实现一个迭代器将其扁平化使之能够按照从左到右的顺序遍历出这个嵌套列表中的所有整数。原文档给出了NestedInteger类需要提供的三个方法这是解题的一切前提方法作用调用前提isInteger()判断当前存储的对象是否为 int无任何对象都可安全调用getInteger()返回当前存储的 int 值仅当isInteger()返回True否则调用会失败getList()返回当前存储的ListNestedInteger仅当isInteger()返回False否则调用会失败例如nestedList [[1, 1], 2, [1, 1]]中第一个元素是包含两个整数的嵌套列表第二个元素是整数2第三个元素又是一个嵌套列表。期望的遍历结果是[1, 1, 2, 1, 1]。二、迭代器接口设计需要实现的扁平化迭代器类NestedIterator包含三个成员NestedIterator(ListNestedInteger 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()被调用时才逐层展开嵌套结构。这正是原文档解题思路的核心其价值在于零预处理成本构造函数只有一次逆序入栈时间复杂度为 $O(L)$$L$ 为最外层元素个数按需计算只有遇到列表时才会展开未被访问的分支永远不会被展开空间可控不需要额外保存扁平化结果栈中始终只保留「待处理边界」。四、栈解法思路详解由于栈具有**后进先出LIFO**的特性参见仓库 03_01_stack_basic.md 对栈顶、栈底、入栈、出栈、查看栈顶的完整定义而我们需要保证「从左到右」的输出顺序因此入栈顺序与目标输出顺序相反。初始化构造函数将nestedList中的所有元素逆序压入栈中。即从最后一个元素开始依次append到栈顶这样栈顶元素就是原列表的第一个元素。hasNext()的核心循环当栈不为空时查看栈顶元素cur如果cur.isInteger()为True说明栈顶就是一个待输出的整数直接返回True否则说明栈顶是一个嵌套列表将其弹出并把它的子元素逆序重新压入栈中保证子元素从左到右排列然后继续循环。如果栈变空说明所有整数都已消费完毕返回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 列表天然支持动态扩容。hasNextcur 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], 2, [1,1]]三个元素。第一次hasNext()栈顶是列表[1,1]弹出并逆序压入1, 1栈变为[[1,1], 2, 1, 1]栈顶1是整数返回True。第一次next()弹出栈顶1返回1。第二次hasNext()next()弹出栈顶1返回1。第三次hasNext()栈顶是整数2返回Truenext()弹出并返回2。第四次hasNext()栈顶是列表[1,1]展开压入两个1返回Truenext()返回1。第五次next()返回最后一个1。第六次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 题解索引 中可按序号顺序刷题。九、面试与实战要点先想清楚hasNext()的职责它不只是「判空」还要负责「推进状态」——把栈顶的嵌套列表展开到栈顶变成整数为止。这是惰性迭代器与普通集合迭代器的最大区别。逆序入栈是核心技巧栈顶必须始终指向「下一个应输出元素」而NestedInteger列表是顺序存储的二者方向相反所以任何层级展开时都要逆序遍历。警惕getInteger()/getList()的误用二者的调用前提是isInteger()的返回值必须在调用前判断否则会失败——这是NestedInteger接口约定的一部分见原文档方法说明。可扩展讨论面试中可进一步讨论如何将该迭代器推广为「任意深度嵌套的通用扁平化工具」、如何支持remove()操作、以及惰性与预展开在时间与空间上的取舍。结论本题的「惰性展开 显式栈」方案将树的递归遍历转化为迭代式遍历是「设计迭代器」类题目的经典范式。掌握它你就同时掌握了栈的逆序使用、hasNext()的状态推进语义以及递归转非递归的核心手法。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐LeetCode 341 扁平化嵌套列表迭代器递归展平与惰性栈四种解法的多语言实现LeetCode 341 扁平化嵌套列表迭代器递归展平与惰性栈四种解法的多语言实现 导读 本文围绕 LeetCode 341「扁平化嵌套列表迭代器Flatt示例工程教程30 seconds of code 实战用生成器与递归实现扁平化迭代嵌套可迭代对象flatIterator30 seconds of code 实战用生成器与递归实现扁平化迭代嵌套可迭代对象flatIterator 导读 在 JavaScript 中 Sym教程文档0385. 迷你语法分析器题解用栈解析整数嵌套列表的 Python 实现0385. 迷你语法分析器题解用栈解析整数嵌套列表的 Python 实现 本篇题解围绕 LeetCode 第 385 题「迷你语法分析器Mini Parse教程文档知识库上一篇终极指南如何快速掌握Hypothesis属性测试从新手到专家下一篇TypeGraphQL中间件开发实战从认证到日志的完整实现创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考