扁平化嵌套列表迭代器

标签: 栈 树 深度优先搜索 设计 队列 迭代器

难度: 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
  • 嵌套列表中的整数值在范围 [-106, 106] 内

Submission

运行时间: 38 ms

内存: 18.7 MB

# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
#class NestedInteger:
#    def isInteger(self) -> bool:
#        """
#        @return True if this NestedInteger holds a single integer, rather than a nested list.
#        """
#
#    def getInteger(self) -> int:
#        """
#        @return the single integer that this NestedInteger holds, if it holds a single integer
#        Return None if this NestedInteger holds a nested list
#        """
#
#    def getList(self) -> [NestedInteger]:
#        """
#        @return the nested list that this NestedInteger holds, if it holds a nested list
#        Return None if this NestedInteger holds a single integer
#        """
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:
        # 返回栈顶元素的整数值
        res = self.stack.pop().getInteger()
        return res

    def hasNext(self) -> bool:
        # 循环检查栈顶元素是否为整数
        while self.stack and not self.stack[-1].isInteger():
            # 如果栈顶元素不是整数，获取其嵌套列表
            temp = self.stack.pop().getList()
            # 将嵌套列表中的元素逆序压入栈中
            for i in range(len(temp) - 1, -1, -1):
                self.stack.append(temp[i])

        # 如果栈为空，返回False；否则，返回True
        if not self.stack:
            return False
        return True




# Your NestedIterator object will be instantiated and called as such:
# i, v = NestedIterator(nestedList), []
# while i.hasNext(): v.append(i.next())

Explain

这个题解使用了一个栈来模拟迭代器的行为。首先将输入的嵌套列表逆序压入栈中。在调用next()方法时，直接返回栈顶元素的整数值。在调用hasNext()方法时，循环检查栈顶元素是否为整数，如果不是，则将其嵌套列表中的元素逆序压入栈中，直到栈顶元素为整数或栈为空。最后根据栈是否为空返回布尔值，表示是否还有下一个整数。

时间复杂度: O(n)

空间复杂度: O(n)

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:
        # 返回栈顶元素的整数值
        res = self.stack.pop().getInteger()
        return res

    def hasNext(self) -> bool:
        # 循环检查栈顶元素是否为整数
        while self.stack and not self.stack[-1].isInteger():
            # 如果栈顶元素不是整数，获取其嵌套列表
            temp = self.stack.pop().getList()
            # 将嵌套列表中的元素逆序压入栈中
            for i in range(len(temp) - 1, -1, -1):
                self.stack.append(temp[i])
        
        # 如果栈为空，返回False；否则，返回True
        if not self.stack:
            return False
        return True

Explore

在初始化时将`nestedList`逆序压入栈中，主要是为了保证当我们弹出栈顶元素进行处理时，这些元素能够保持其原始的顺序。由于栈是先进后出的数据结构，逆序压栈确保我们在后续的迭代中首先访问到最前面的元素，符合迭代器从前向后访问元素的直觉。如果不逆序，那么我们访问的顺序将是颠倒的，这与期望的行为不符。

将非整数的嵌套列表元素逆序压入栈的过程确实会对迭代器的性能产生影响。在嵌套结构复杂的情况下，这种影响可能更加明显。每次遇到嵌套列表时，都需要将其内容逆序并压栈，这增加了操作的复杂度。然而，这种复杂度是不可避免的，因为我们需要完全展开嵌套结构以访问所有的整数。尽管如此，每个元素最多被处理一次，所以算法的时间复杂度仍然是线性的，与元素的总数成正比。

正常的使用情况下，应当在调用`next`方法之前调用`hasNext`方法来确保栈顶元素是整数。`hasNext`方法的设计就是为了检查栈顶元素，如果栈顶元素不是整数，则会将其嵌套列表展开直到栈顶是整数或栈空。如果直接调用`next`而不先调用`hasNext`，可能会导致错误，如尝试从空栈中弹出元素或处理非整数元素，因此这种使用方式是不安全的。

是的，虽然每个元素最多被处理一次确保了算法的时间复杂度为O(n)，其中n是嵌套列表中元素的总数，但实际的性能还是会受到列表结构的影响。深度和分支数量的增加可能会使得栈操作更频繁，因为需要更多的压栈和弹栈操作来处理更复杂的嵌套结构。尽管总的处理次数仍然与元素总数成正比，但更复杂的结构可能导致实际执行时间增加，因为每次处理嵌套列表时都涉及到栈的多次操作。