个人评价：设计迭代器 =》DFS递归；嵌套可使用栈；另考验了一定的理解能力和基础建模

题目难度：🌟 🌟 （参考 LeeCode 简单🌟 、中等🌟 🌟 、困难🌟 🌟 🌟 ）

另，通常算法题会考察分析时间复杂度和空间复杂度，可参考笔者之前的文章

「数据结构&算法」必知必会系列：3. 时间 & 空间复杂度（下）

扁平化嵌套列表迭代器

题目描述

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

给你一个嵌套的整型列表。请你设计一个迭代器，使其能够遍历这个整型列表中的所有整数。

列表中的每一项或者为一个整数，或者是另一个列表。其中列表的元素也可能是整数或是其他列表。

示例 1:

输入: [[1,1],2,[1,1]]

输出: [1,1,2,1,1]

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

示例 2:

输入: [1,[4,[6]]]

输出: [1,4,6]

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

解题思路

方法一

如果只是单纯的展开嵌套 list，不难解，确认最小粒度的元素：整数/整数数组

所以，关键是展开的递归函数，Golang 实现如下：

func flatten(n *NestedInteger) []int {
    res := []int{}
    if n.IsInteger() { // 是否数字
        res = append(res, n.GetInteger()) // 加入数字
    } else { // 非数字
        for _, child := range n.GetList() {
            res = append(res, flatten(child)...) // 递归
        }
    }
    return res // 返回扁平后的结果数组
}

构造类型（struct）NestedIterator，从题目中，我们了解到需要记录第一层数组的遍历下标，因此构建类型、对应的构建数组利用了上述 flatten 方法。

Golang 实现参考如下：

type NestedIterator struct {
    vals []int // 展开后的数组
    index int  // index是当前 Next调用应该返回的 第index个数
}

func Constructor(nestedList []*NestedInteger) *NestedIterator {
    list := []int{}
    for _, n := range nestedList { // 遍历nestedList
      list = append(list, flatten(n)...) // 当前元素 append flatten(n)
    }
    return &NestedIterator{index: 0, vals: list} // 创建并返回迭代器，初始下标index为0
}

Next() 方法和判断是否结束 HasNext() 应该不难理解

func (this *NestedIterator) Next() int {
    val := this.vals[this.index] // 获取元素
    this.index++                 // 更新index
    return val
}

func (this *NestedIterator) HasNext() bool {
    return this.index < len(this.vals)
}

复杂度？

  • 时间复杂度：初始化为 O(n)，其中 n 是嵌套的整型列表中的元素个数。Next() 操作 O(1)
  • 空间复杂度：O(n) 需要一个数组存储嵌套的整型列表中的所有元素

方法二

参考网友解法，解释蛮精辟的，啊哈哈~

栈像一个劳改营，元素从后往前一个个入栈（前面元素后进去，栈后进先出，Next能先拿到前面元素），进栈了大家暂时相安无事。

等到Next调用时，要拿integer了，才忙活起来，整顿一下栈顶

审查一下栈顶元素，是integer就没事，是嵌套list 就pop出来，把它里面的元素一个个再塞入栈

有可能新的栈顶还不是 integer，继续上述操作，直到栈顶是 integer 或栈空了

这样整顿后，要么栈空了，要么栈顶一定是integer了

作者：xiao_ben_zhu 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处

来源：力扣（LeetCode）链接

type NestedIterator struct {
	Stack []*NestedInteger // 栈是用来暂存元素的
}

func Constructor(nestedList []*NestedInteger) *NestedIterator {
	stack := []*NestedInteger{}
	for i := len(nestedList) - 1; i >= 0; i-- { // 将元素从后开始一个个入栈
		stack = append(stack, nestedList[i]) // 从后是因为后进先出，位于前面的要先出
	}
	return &NestedIterator{Stack: stack} // 初始化并返回这个迭代器
}

func (this *NestedIterator) Next() int {
	this.stackTop2Integer()                     // 将栈顶元素转成integer
	top := this.Stack[len(this.Stack)-1]        // 获取栈顶
	this.Stack = this.Stack[:len(this.Stack)-1] // pop掉栈顶
	return top.GetInteger()                     // 返回integer
}

func (this *NestedIterator) HasNext() bool {
	this.stackTop2Integer()    // 将栈顶元素转成integer
	return len(this.Stack) > 0 // 如果stack没有空。说明能获取到integer
}

// 将栈顶元素变成integer（通过将list栈顶pop出来，再将它里面的元素一个个再放进去）
func (this *NestedIterator) stackTop2Integer() {
	for len(this.Stack) > 0 { // 直到栈空了
		top := this.Stack[len(this.Stack)-1] // 获取栈顶
		if top.IsInteger() {                 // 栈顶已经是integer，什么都不做
			return
		}
		this.Stack = this.Stack[:len(this.Stack)-1] // 栈顶是list，弹出栈顶
		list := top.GetList()                       // 获取list
		for i := len(list) - 1; i >= 0; i-- {       // 从后开始遍历list
			this.Stack = append(this.Stack, list[i])  // 将list的元素推入栈
		}
	}
}

总结

个人感觉此题使用递归暴力展开即可，需要一定的理解力还有递归使用方法。

栈的使用利于 Next() 时一个个操作，而无须构建时就一一展开。

等到Next调用时，要拿integer了，才忙活起来，整顿一下栈顶 <(￣▽￣)/