Medium

题目描述

给你一个嵌套的整数列表 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 直到 hasNext 返回 false，next 返回的元素的顺序应该是: [1,1,2,1,1]。

示例 2：

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

提示：

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

解题思路

解题思路

这道题要求实现一个迭代器来扁平化嵌套列表。有两种主要思路：

方法一：预处理扁平化（推荐）

在构造函数中直接将整个嵌套列表展开成一个普通的整数数组，然后用一个指针来遍历这个数组。优点是实现简单，next() 和 hasNext() 都是 O(1) 操作。

方法二：栈模拟递归

使用栈来模拟深度优先遍历的过程。在 hasNext() 中确保栈顶元素是一个整数，如果栈顶是列表则将其展开并放回栈中。这种方法的优点是惰性求值，只在需要时才处理元素。

对于大多数场景，预处理方法更简单直观，因为题目约束较小（最多500个元素），预处理的空间开销可以接受。而栈方法在处理超大数据或者内存受限的场景下更有优势。

两种方法的时间复杂度都是 O(n)，其中 n 是所有整数的总数。空间复杂度也都是 O(n)。这里采用预处理的方法作为主要解法。

代码实现

class NestedIterator {
private:
    vector<int> nums;
    int index;
    
    void dfs(const vector<NestedInteger>& nestedList) {
        for (const auto& nested : nestedList) {
            if (nested.isInteger()) {
                nums.push_back(nested.getInteger());
            } else {
                dfs(nested.getList());
            }
        }
    }
    
public:
    NestedIterator(vector<NestedInteger> &nestedList) {
        index = 0;
        dfs(nestedList);
    }
    
    int next() {
        return nums[index++];
    }
    
    bool hasNext() {
        return index < nums.size();
    }
};

class NestedIterator:
    def __init__(self, nestedList: [NestedInteger]):
        self.nums = []
        self.index = 0
        self._flatten(nestedList)
    
    def _flatten(self, nestedList):
        for nested in nestedList:
            if nested.isInteger():
                self.nums.append(nested.getInteger())
            else:
                self._flatten(nested.getList())
    
    def next(self) -> int:
        result = self.nums[self.index]
        self.index += 1
        return result
    
    def hasNext(self) -> bool:
        return self.index < len(self.nums)

public class NestedIterator {
    private List<int> nums;
    private int index;
    
    public NestedIterator(IList<NestedInteger> nestedList) {
        nums = new List<int>();
        index = 0;
        Flatten(nestedList);
    }
    
    private void Flatten(IList<NestedInteger> nestedList) {
        foreach (var nested in nestedList) {
            if (nested.IsInteger()) {
                nums.Add(nested.GetInteger());
            } else {
                Flatten(nested.GetList());
            }
        }
    }

    public bool HasNext() {
        return index < nums.Count;
    }

    public int Next() {
        return nums[index++];
    }
}

var NestedIterator = function(nestedList) {
    this.nums = [];
    this.index = 0;
    this.flatten(nestedList);
};

NestedIterator.prototype.flatten = function(nestedList) {
    for (let nested of nestedList) {
        if (nested.isInteger()) {
            this.nums.push(nested.getInteger());
        } else {
            this.flatten(nested.getList());
        }
    }
};

NestedIterator.prototype.hasNext = function() {
    return this.index < this.nums.length;
};

NestedIterator.prototype.next = function() {
    return this.nums[this.index++];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
构造函数O(n)O(n)
next()O(1)O(1)
hasNext()O(1)O(1)

其中 n 是嵌套列表中所有整数的总数。构造函数需要遍历所有元素进行扁平化，空间复杂度为存储所有整数所需的空间。

相关题目