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

Categories:

题目描述
思路分析
1. 解法一：栈模拟（推荐）
相似题目

题目描述

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

思路分析

解法一：栈模拟（推荐）

核心思路：

使用栈保存待遍历的 NestedInteger。

hasNext 展开栈顶，确保栈顶为整数。

next 直接弹出整数。

复杂度分析：

时间复杂度：均摊 O(1)，每个元素仅处理一次。

空间复杂度：O(n)，用于栈存储。

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Iterator;
import java.util.List;

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() {
        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
}

相似题目

题目	难度	考察点
385. 迷你语法分析器	中等	栈
339. 嵌套列表权重和	中等	递归
364. 加权嵌套序列和 II	中等	递归
251. 展开二维向量	中等	迭代器
341. 扁平化嵌套列表迭代器	中等	迭代器

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/19439487