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

🟠   🔖  栈 树 深度优先搜索 设计 队列 迭代器  🔗 力扣 LeetCode

题目

You are given a nested list of integers nestedList. Each element is either an integer or a list whose elements may also be integers or other lists. Implement an iterator to flatten it.

Implement the NestedIterator class:

• NestedIterator(List<NestedInteger> nestedList) Initializes the iterator with the nested list nestedList.
• int next() Returns the next integer in the nested list.
• boolean hasNext() Returns true if there are still some integers in the nested list and false otherwise.

Your code will be tested with the following pseudocode:

initialize iterator with nestedList
res = []
while iterator.hasNext()
  append iterator.next() to the end of res
return res

If res matches the expected flattened list, then your code will be judged as correct.

Example 1:

Input: nestedList = [[1,1],2,[1,1]]

Output: [1,1,2,1,1]

Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,1,2,1,1].

Example 2:

Input: nestedList = [1,[4,[6]]]

Output: [1,4,6]

Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,4,6].

Constraints:

• 1 <= nestedList.length <= 500
• The values of the integers in the nested list is in the range [-10^6, 10^6].

题目大意

给你一个嵌套的整数列表 nestedList 。每个元素要么是一个整数，要么是一个列表；该列表的元素也可能是整数或者是其他列表。请你实现一个迭代器将其扁平化，使之能够遍历这个列表中的所有整数。

实现扁平迭代器类 NestedIterator ：

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

你的代码将会用下述伪代码检测：

initialize iterator with nestedList
res = []
while iterator.hasNext()
  append iterator.next() to the end of res
return res

如果 res 与预期的扁平化列表匹配，那么你的代码将会被判为正确。

示例 1：

输入： nestedList = [[1,1],2,[1,1]]

输出：[1,1,2,1,1]

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

示例 2：

输入： nestedList = [1,[4,[6]]]

输出：[1,4,6]

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

提示：

• 1 <= nestedList.length <= 500
• 嵌套列表中的整数值在范围 [-10^6, 10^6] 内

解题思路

利用递归深度优先搜索（DFS）将嵌套列表展开为一个扁平化数组，随后通过两个指针进行迭代。

1. 初始化阶段

   • 使用一个私有方法 dfs() 遍历嵌套列表，递归处理每个元素。
   • 如果是整数，直接加入结果数组。
   • 如果是列表，递归调用 dfs() 继续展开。
   • 最终将扁平化的结果存储在一个数组 flatten 中。

2. hasNext() 方法

   • 检查当前指针是否小于扁平化数组的长度。

3. next() 方法

   • 返回当前指针指向的整数，同时将指针向后移动。

复杂度分析

• 时间复杂度：

  • 初始化（dfs）：需要遍历整个嵌套列表，时间复杂度为 O(n)，其中 n 是列表中所有整数和列表的总数。
  • hasNext() 和 next()：每次调用的时间复杂度为 O(1)。

• 空间复杂度：O(n)，额外使用的空间为存储扁平化数组的空间。

代码

class NestedIterator {
	constructor(nestedList) {
		this.cur = 0; // 当前指针
		this.flatten = this.dfs(nestedList); // 扁平化后的数组
	}

	// 深度优先搜索展开列表
	dfs(arr) {
		let res = [];
		for (let item of arr) {
			if (item.isInteger()) {
				// 如果是整数，直接加入结果数组
				res.push(item.getInteger());
			} else {
				// 如果是列表，递归展开
				res.push(...this.dfs(item.getList()));
			}
		}
		return res;
	}

	// 判断是否还有下一个整数
	hasNext() {
		return this.cur < this.flatten.length;
	}

	// 返回当前整数并移动指针
	next() {
		return this.flatten[this.cur++];
	}
}

相关题目

题号	标题	题解	标签	难度	力扣
251	展开二维向量 🔒		设计 数组 双指针 1+	🟠	🀄️ 🔗
281	锯齿迭代器 🔒		设计 队列 数组 1+	🟠	🀄️ 🔗
385	迷你语法分析器		栈 深度优先搜索 字符串	🟠	🀄️ 🔗
565	数组嵌套		深度优先搜索 数组	🟠	🀄️ 🔗