LeetCode 第341题：扁平化嵌套列表迭代器

📖 文章摘要

本文详细解析LeetCode第341题“扁平化嵌套列表迭代器”，这是一道中等难度的设计题。文章提供了基于栈和递归的解法，包含C#、Python、C++三种语言实现，配有详细的算法分析和性能对比。适合想要提升迭代器设计和数据结构处理能力的程序员。

核心知识点： 迭代器设计、栈、递归、数据结构
难度等级： 中等
推荐人群： 具有基础数据结构知识，想要提升迭代器设计能力的程序员

题目描述

给你一个嵌套的整型列表。请你设计一个迭代器，使其能够遍历这个整型列表中的所有整数。

列表中的每一项或者为一个整数，或者是另一个列表。其中列表的元素也可能是整数或是其他列表。

示例

示例 1：

输入：[[1,1],2,[1,1]]
输出：[1,1,2,1,1]
解释：通过重复调用 next 直到 hasNext 返回 false，next 返回的元素的顺序应该是: [1,1,2,1,1]。

示例 2：

输入：[1,[4,[6]]]
输出：[1,4,6]
解释：通过重复调用 next 直到 hasNext 返回 false，next 返回的元素的顺序应该是: [1,4,6]。

提示

嵌套列表中的整数值在范围 [-10^6, 10^6] 内
嵌套列表的最大深度小于或等于 1000

解题思路

方法一：栈

使用栈来存储和处理嵌套列表的元素。

关键点：

使用栈存储列表元素
倒序压入栈中以保持正确顺序
延迟处理嵌套列表
提前处理下一个元素

具体步骤：

构造函数中初始化栈
hasNext()中确保栈顶是整数
next()返回栈顶整数
处理嵌套列表时递归展开

时间复杂度：

构造函数：O(n)
hasNext(): 均摊O(1)
next(): O(1)

空间复杂度：O(n)

方法二：递归预处理

在构造时就将嵌套列表完全展开。

关键点：

递归展开所有嵌套列表
使用队列存储展开后的整数
一次性完成展开操作
简化后续操作

图解思路

栈方法分析表

操作	栈内容	当前元素	说明
初始化	[[1,1],2,[1,1]]	-	原始列表
压栈	[1,1],2,[1,1]	-	倒序压入
next()	1	1	返回第一个数
next()	1,2,[1,1]	1	返回第二个数
next()	2,[1,1]	2	返回第三个数

递归展开分析

输入：[1,[4,[6]]]
展开过程：
1. 遇到1：直接加入结果
2. 遇到[4,[6]]：递归处理
   2.1 遇到4：加入结果
   2.2 遇到[6]：递归处理
      2.2.1 遇到6：加入结果
最终结果：[1,4,6]

代码实现

C# 实现

public class NestedIterator {
    private Stack<NestedInteger> stack;
    
    public NestedIterator(IList<NestedInteger> nestedList) {
        stack = new Stack<NestedInteger>();
        // 倒序压入栈中
        for (int i = nestedList.Count - 1; i >= 0; i--) {
            stack.Push(nestedList[i]);
        }
    }
    
    public bool HasNext() {
        // 确保栈顶是整数
        while (stack.Count > 0 && !stack.Peek().IsInteger()) {
            var list = stack.Pop().GetList();
            // 倒序压入栈中
            for (int i = list.Count - 1; i >= 0; i--) {
                stack.Push(list[i]);
            }
        }
        return stack.Count > 0;
    }
    
    public int Next() {
        return stack.Pop().GetInteger();
    }
}

Python 实现

class NestedIterator:
    def __init__(self, nestedList: [NestedInteger]):
        self.stack = []
        # 倒序压入栈中
        for i in range(len(nestedList)-1, -1, -1):
            self.stack.append(nestedList[i])
    
    def next(self) -> int:
        return self.stack.pop().getInteger()
    
    def hasNext(self) -> bool:
        # 确保栈顶是整数
        while self.stack and not self.stack[-1].isInteger():
            nested_list = self.stack.pop().getList()
            # 倒序压入栈中
            for i in range(len(nested_list)-1, -1, -1):
                self.stack.append(nested_list[i])
        return len(self.stack) > 0

C++ 实现

class NestedIterator {
private:
    stack<NestedInteger> st;
    
public:
    NestedIterator(vector<NestedInteger> &nestedList) {
        // 倒序压入栈中
        for (int i = nestedList.size() - 1; i >= 0; i--) {
            st.push(nestedList[i]);
        }
    }
    
    int next() {
        int result = st.top().getInteger();
        st.pop();
        return result;
    }
    
    bool hasNext() {
        // 确保栈顶是整数
        while (!st.empty() && !st.top().isInteger()) {
            auto nestedList = st.top().getList();
            st.pop();
            // 倒序压入栈中
            for (int i = nestedList.size() - 1; i >= 0; i--) {
                st.push(nestedList[i]);
            }
        }
        return !st.empty();
    }
};

执行结果

C# 实现

执行用时：144 ms
内存消耗：46.2 MB

Python 实现

执行用时：64 ms
内存消耗：17.8 MB

C++ 实现

执行用时：12 ms
内存消耗：12.9 MB

性能对比

语言	执行用时	内存消耗	特点
C#	144 ms	46.2 MB	代码结构清晰
Python	64 ms	17.8 MB	实现最简洁
C++	12 ms	12.9 MB	性能最优

代码亮点

🎯 优雅的迭代器设计
💡 高效的栈操作
🔍 延迟处理策略
🎨 清晰的代码结构

常见错误分析

🚫 忘记处理嵌套列表
🚫 栈操作顺序错误
🚫 hasNext判断不当
🚫 递归深度过大

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
栈	O(n)	O(n)	延迟处理	代码复杂
递归预处理	O(n)	O(n)	实现简单	内存占用大

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新至第341题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

👍 点个赞，让更多人看到这篇文章
📁 收藏文章，方便后续查阅复习
🔔 关注作者，获取更多高质量算法题解
💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！

📖 文章摘要

题目描述

示例

示例 1：

示例 2：

提示

解题思路

方法一：栈

方法二：递归预处理

图解思路

栈方法分析表

递归展开分析

代码实现

C# 实现

Python 实现

C++ 实现

执行结果

C# 实现

Python 实现

C++ 实现

性能对比

代码亮点

常见错误分析

解法对比

相关题目

📖 系列导航

💬 互动交流