各位题友大家好！ 今天是 @负雪明烛 坚持日更的第 58 天。今天力扣上的每日一题是「341. 扁平化嵌套列表迭代器」。

题意解析

今天的题意略难理解，需要我翻译一下，理解题意的朋友请跳过。

本题定义了一个类 NestedInteger ，这个类可以存储 int 或 List<NestedInteger> ；所以称它是一个「嵌套列表」。类似于一棵多叉树，每个节点都可以有很多子节点。

它有三个方法：

  • isInteger() ，判断当前存储的对象是否为 int；
  • getInteger() , 如果当前存储的元素是 int 型的，那么返回当前的结果 int，否则调用会失败；
  • getList() ，如果当前存储的元素是 List<NestedInteger> 型的，那么返回该 List，否则调用会失败。

而「扁平化嵌套列表迭代器」说的是，我们需要设计一个迭代器，这个迭代器是把「嵌套列表」铺平（拆包）成各个 int，然后每次调用 hasNext() 来判断是否有下一个整数，通过 next() 返回下一个整数。

注意迭代器是一种按照特定顺序对数据结构遍历的方式，它的调用方式是：

  1. i, v = NestedIterator(nestedList), []
  2. while i.hasNext():
  3.     v.append(i.next())

解题思路

本文有两种主要的思路：
1. 在构造函数中提前「扁平化」整个嵌套列表；
2. 在调用 hasNext() 或者 next() 方法的时候扁平化当前的嵌套的子列表。

一、构造函数中提前「扁平化」整个嵌套列表

这是最简单的方法，但是我认为这不是面试官想要的方法。

在构造函数中提前扁平化整个嵌套列表。那么在 hasNext() 或者 next() 可以很简单地返回迭代器位置的 int。

因为这个嵌套的数据结构有点类似于多叉树，所以我们可以按照类似地遍历思路：递归。

承载遍历结果的数据结构可以使用数组，那么另外需要一个整数标记当前的迭代器指向的位置；也可以使用一个队列，每次调用 next() 方法的时候从队列的开头弹出一个元素。

递归的思路比较简单，我用的是队列：

  • 遍历输入的「嵌套列表」所有的元素，判断每个元素是 int 还是 list；
    • 如果当前元素是 int，放入队列尾部；
    • 如果当前元素是 list，那么需要对当前 子list 继续递归；

其余代码比较简单，不作赘述。

  1. class NestedIterator(object):
  2.     def dfs(self, nests):
  3.         for nest in nests:
  4.             if nest.isInteger():
  5.                 self.queue.append(nest.getInteger())
  6.             else:
  7.                 self.dfs(nest.getList())
  9.     def __init__(self, nestedList):
  10.         self.queue = collections.deque()
  11.         self.dfs(nestedList)
  13.     def next(self):
  14.         return self.queue.popleft()
  16.     def hasNext(self):
  17.         return len(self.queue)
  • 时间复杂度：构造函数的时间复杂度是 $O(N)$； next() 和 hasNext() 的时间复杂度是 $O(1)$。
  • 空间复杂度：$O(N)$。

二、调用 hasNext() 或者 next() 方法的时候扁平化当前的嵌套的子列表

**
这个方法更加有挑战性，也是这个题最正确的解法。因为对于大部分情况，我们希望迭代器能够一边迭代一边获取当前的结果，而不是提前初始化好。

把递归方法 转 迭代方法，我们需要用到「栈」。

在递归方法中，我们在遍历时如果遇到一个嵌套的 子list，就立即处理该 子list，直到全部展开；
在迭代方法中，我们不需要全部展开，只需要把 当前list 的所有元素放入 list 中。

由于「栈」的先进后出的特性，我们需要逆序在栈里放入各个元素。

处理流程分为两步：
1. 在构造函数中应该初始化，把当前列表的各个元素（不用摊平）逆序放入栈中。
2. 在 hasNext() 方法中，访问（不弹出）栈顶元素，判断是否为 int：

  • 如果是 int 那么说明有下一个元素，返回 true；然后 next() 就会被调用，把栈顶的 int 弹出；
  • 如果是 list 需要把当前列表的各个元素（不用摊平）逆序放入栈中。
  • 如果栈为空，那么说明原始的嵌套列表已经访问结束了，返回 false。

算法整体的流程，通过举例说明。假如输入 [1, [2,3]] 。

  1. 1. 在构造函数中：栈里面放的应该是 stack = [[2, 3], 1]
  2. 2. 在调用 `hasNext()` 方法时，访问栈顶元素是 1，为 int，那么直接返回 true;
  3. 3. 然后调用 `next()` 方法，弹出栈顶元素 1；
  4. 4. 再调用 `hasNext()` 方法时，访问栈顶元素是 [2,3]，为 list，那么需要摊平，继续放到栈中。
  5.         当前的栈是 stack = [3, 2]
  6. 5. 然后调用 `next()` 方法，弹出栈顶元素 2；
  7. 6. 然后调用 `next()` 方法，弹出栈顶元素 3；
  8. 7. 再调用 `hasNext()` 方法时，栈为空，因此返回 false，迭代器运行结束。

这里需要说一下为什么在 hasNext() 方法中摊平 list，而不是在 next() 方法中。比如对于 [[]] 的输入， hasNext() 方法是判断其中是否有 int 元素了，则必须把内层的 list 摊平来看，发现是空的，返回 false。

代码如下：

  2. class NestedIterator(object):
  4.     def __init__(self, nestedList):
  5.         self.stack = []
  6.         for i in range(len(nestedList) - 1, -1, -1):
  7.             self.stack.append(nestedList[i])
  10.     def next(self):
  11.         cur = self.stack.pop()
  12.         return cur.getInteger()
  14.     def hasNext(self):
  15.         while self.stack:
  16.             cur = self.stack[-1]
  17.             if cur.isInteger():
  18.                 return True
  19.             self.stack.pop()
  20.             for i in range(len(cur.getList()) - 1, -1, -1):
  21.                 self.stack.append(cur.getList()[i])
  22.         return False
  1. class NestedIterator {
  2. public:
  3.     NestedIterator(vector<NestedInteger> &nestedList) {
  4.         for (int i = nestedList.size() - 1; i >= 0; --i) {
  5.             st.push(nestedList[i]);
  6.         }
  7.     }
  9.     int next() {
  10.         NestedInteger cur = st.top(); st.pop();
  11.         return cur.getInteger();
  12.     }
  14.     bool hasNext() {
  15.         while (!st.empty()) {
  16.             NestedInteger cur = st.top();
  17.             if (cur.isInteger()) {
  18.                 return true;
  19.             }
  20.             st.pop();
  21.             for (int i = cur.getList().size() - 1; i >= 0; --i) {
  22.                 st.push(cur.getList()[i]);
  23.             }
  24.         }
  25.         return false;
  26.     }
  27. private:
  28.     stack<NestedInteger> st;
  29. };
  • 时间复杂度：构造函数的最坏时间复杂度是 $O(N)$； next() 和 hasNext() 的最坏时间复杂度是 $O(N)$。
  • 空间复杂度：$O(N)$。

刷题心得

面试的时候需要写出方法二，今天的题目很好，请务必掌握呀。

参考资料：
力扣官方题解
341. Flatten Nested List Iterator

OK，以上就是 @负雪明烛 写的今天题解的全部内容了，如果你觉得有帮助的话，求赞、求关注、求收藏。如果有疑问的话，请在下面评论，我会及时解答。

关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。

祝大家牛年大吉！AC 多多，Offer 多多！我们明天再见！