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

约 5 分钟
文章信息 8 个分类 6 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 腾讯 字节 微软
标签
深度优先搜索 树 栈 设计 队列 迭代器

题目描述

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

image-20260928223834953

image-20260928223834954

题意分析

输入是一个嵌套列表，每一项要么是整数，要么是仍可继续嵌套的列表。需要按原始从左到右的顺序逐个返回全部整数，空列表不产生任何输出，列表本身也不是返回值。

迭代器需要在多次方法调用之间保存进度。hasNext 判断是否还存在下一个整数，next 取得这个整数。题目给出的测试流程是先调用 hasNext，返回真后才调用 next；本实现让前者准备好下一个值，后者只负责消费它。

解法：栈模拟

核心思路

[!blue]

用显式栈保存尚未消费的嵌套项，栈顶表示接下来最先处理的一项。构造时将顶层列表从后向前压栈，抵消栈后进先出的顺序，使原来的第一项位于栈顶。

若栈顶已经是整数，它就是接下来应返回的值；若栈顶是列表，就先弹出这个列表，再把它的子项逆序压入。子项会位于原来其他待处理项之上，因此整棵当前子列表会先被处理，之后才轮到外层的下一个兄弟项，保持嵌套结构的原始顺序。

准备下一个值不能只展开一次。列表里面可能仍然是列表，也可能为空，因此 hasNext 持续展开栈顶，直到发现整数或栈清空。空列表被弹出后不压入任何项，继续检查后面的工作；所以栈非空并不等于一定还有整数。

发现栈顶为整数时，hasNext 返回真但不弹出它。这样连续多次询问可用性仍会看到同一个整数，不会跳过数据。只有调用 next 时才弹出这个已准备的整数，让迭代进度前进一步。

每个嵌套项至多入栈、出栈一次，不提前把所有整数复制到单独数组。栈保存的是尚未处理的工作，并不表示其中所有列表都已展开；处理会随着调用逐步发生。

解题步骤

  1. 构造时将顶层各项逆序压栈。
  2. hasNext 中反复检查栈顶：整数则返回真，列表则弹出并逆序压入它的子项。
  3. 若展开后栈清空，返回假，表示后面已经没有整数。
  4. 按题目调用协议，在 hasNext 返回真后，next 弹出栈顶并返回其整数值。

代码实现

public class NestedIterator implements Iterator<Integer> {
    private final Deque<NestedInteger> stack = new ArrayDeque<>();

    public NestedIterator(List<NestedInteger> nestedList) {
        // 逆序入栈，让原列表最前项先被处理
        for (int i = nestedList.size() - 1; i >= 0; i--) {
            stack.push(nestedList.get(i));
        }
    }

    @Override
    public Integer next() {
        return stack.pop().getInteger();
    }

    @Override
    public boolean hasNext() {
        // hasNext 负责把栈顶列表展开到栈顶为整数。
        while (!stack.isEmpty()) {
            NestedInteger top = stack.peek();

            // 只检查不消费，重复询问仍保留同一个整数
            if (top.isInteger()) {
                return true;
            }

            // 先移除待展开列表，再将子项逆序压入
            stack.pop();
            List<NestedInteger> list = top.getList();

            for (int i = list.size() - 1; i >= 0; i--) {
                stack.push(list.get(i));
            }
        }

        return false;
    }
}

type NestedIterator struct {
    // 为了保持原始顺序，向栈中放入列表元素时必须从后往前压入。
    stack []*NestedInteger
}

func Constructor(nestedList []*NestedInteger) *NestedIterator {
    stack := make([]*NestedInteger, 0, len(nestedList))
    // 逆序入栈，让原列表最前项先被处理
    for i := len(nestedList) - 1; i >= 0; i-- {
        stack = append(stack, nestedList[i])
    }
    return &NestedIterator{stack: stack}
}

func (it *NestedIterator) Next() int {
    n := it.stack[len(it.stack)-1]
    it.stack = it.stack[:len(it.stack)-1]
    return n.GetInteger()
}

func (it *NestedIterator) HasNext() bool {
    for len(it.stack) > 0 {
        top := it.stack[len(it.stack)-1]
        // 只检查不消费，重复询问仍保留同一个整数
        if top.IsInteger() {
            return true
        }

        // 先移除待展开列表，再将子项逆序压入
        it.stack = it.stack[:len(it.stack)-1]
        list := top.GetList()
        for i := len(list) - 1; i >= 0; i-- {
            it.stack = append(it.stack, list[i])
        }
    }
    return false
}

复杂度分析

设顶层项数为 k，所有层的整数项与列表项合计为 N，可用性检查调用次数为 Q。

  • 时间复杂度：构造为 $O(k)$；完成全部遍历及 Q 次 hasNext 共 $O(N + Q)$。每个嵌套项只展开或消费一次，但一次 hasNext 可能连续经过大量列表，最坏为 $O(N)$；已经准备好的 next 为 $O(1)$。
  • 空间复杂度：$O(N)$，显式栈可能同时保存大量尚未处理的兄弟项，不能只按嵌套深度估计。

关键点总结

[!green]

  • 栈顶表示下一项工作，子列表逆序入栈保证其内部与外部的读取顺序。
  • 可用性检查允许展开结构，但不能消费已经准备好的整数。
  • 复杂度按所有嵌套项计数，空列表虽然不输出整数，仍然需要处理。

易错点总结

[!yellow]

  • 正序压栈会让列表最后一项先被读取，颠倒原始顺序。
  • 只展开一层就返回真，可能把更深列表或空列表误当作可用整数。
  • 展开子项前不弹出原列表，会在之后反复处理同一列表。
  • hasNext 找到整数时就把它弹出，会让重复检查跳过数据。
  • 仅检查栈是否非空，无法判断剩余内容是否全部为空列表。
  • 把每次 hasNext 都写成常数时间，忽略了它可能一次展开多层或多项结构。

相似题目

题目 难度 关联与区别
251. 展开二维向量 中等 二维向量只需行列游标，本题嵌套深度不固定，需要栈或递归保存展开状态。
385. 迷你语法分析器 中等 原题把文本解析成嵌套整数结构，本题遍历已经构造好的结构并延迟展开。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/19439487
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！