请设计并实现一个能够展开二维向量的迭代器。该迭代器需要支持
next 和 hasNext 两种操作。实现
Vector2D 类：Vector2D(int[][] vec)使用二维向量vec初始化对象
next()从二维向量返回下一个元素并将指针移动到下一个位置。你可以假设对next的所有调用都是合法的。
hasNext()当向量中还有元素返回true，否则返回false。
示例 1：
这道题表面上是“把二维数组拍平成一维数组”，但它真正考察的是 Iterator 设计。
Iterator 的核心价值是：按需返回下一个元素，而不是一开始就把所有元素都复制出来。
所以这题有两种典型思路：
- 构造函数里直接 flatten，之后像普通一维数组一样遍历；
- 只维护两个指针，按需跳过空行，真正做到惰性遍历。
解法一：构造时直接 flatten
最直观的做法是，在构造函数
__init__ 里把整个二维数组展开成一个一维列表。比如：
可以预处理成：
之后
next() 只需要返回 nums[pos]，然后 pos += 1；hasNext() 只需要判断 pos < len(nums)。这个解法的 intuition 很简单：既然最终遍历顺序就是一维顺序，那就先把数据变成一维，再写普通 iterator。
复杂度分析
设
N 是二维数组中的整数总数，V 是内层数组的数量。- 时间复杂度:
- 构造函数:
O(N + V) next():O(1)hasNext():O(1)
因为即使某些内层数组为空，也仍然要遍历这些行；同时需要把所有
N 个整数复制到新列表中。- 空间复杂度:
O(N)
因为额外创建了一个一维列表保存所有整数。
这份代码可以工作，而且很容易写。但从 iterator 设计角度看，它不够好。
Iterator 的一个重要目标是 lazy evaluation，也就是调用方要一个元素，我们才处理一个元素。如果构造函数里直接 flatten，那么即使调用方只调用一次
next()，我们也已经提前扫描并复制了整个二维数组。如果输入很大，甚至来自文件、网络流或其他无法一次性全部加载的数据源，这种设计就不合适。
所以它更像是
getFlattenedVector(vec), 而不是一个真正意义上的 lazy iterator。解法二：双指针 —— 惰性跳过空行 （推荐）
更好的做法是只维护当前位置。二维数组中，一个元素的位置由两个下标决定：
i = 当前行, j = 当前列初始时:
i = 0, j = 0但二维数组里可能有空行，比如
[[], [1, 2], [], [3]] 。所以我们需要一个辅助函数
forward()，负责把 (i, j) 推进到下一个合法元素。所谓合法元素，就是
i < len(vec) and j < len(vec[i])如果当前行为空，或者当前行已经走完，就不断移动到下一行，并把
j 重置为 0。用一个复杂函数
forward()。调用 forward() 后，要么 (i, j) 指向一个合法元素，要么 i == len(vec)，表示已经没有元素了。这样：hasNext()只需要调用forward()，然后判断是否还有合法行；
next()也先调用forward()，然后返回当前元素，并让j += 1。
特别重要的一点是：
hasNext() 可以被连续调用多次，但不应该跳过元素。所以 forward() 只有在当前 (i, j) 不合法时才移动指针；如果已经指向合法元素，它什么都不做。Walk Through Example
以
vec = [[], [1, 2], [], [3]]为例：初始
(i, j) = (0, 0)，第 0 行为空，所以 forward() 会跳到第 1 行，指向 1。
调用 next() 返回 1 后，j 变成 1，继续返回 2。
当第 1 行走完后，forward() 会跳过空的第 2 行，来到第 3 行，最终返回 3。复杂度分析
设
N 是整数总数，V 是内层数组数量。- 时间复杂度：
- 构造函数：
O(1)，因为只保存输入引用和两个指针。 next()/hasNext()的 均摊时间复杂度：O(1)
next() 和 hasNext() 的单次最坏时间复杂度不一定是严格 O(1)。比如连续遇到很多空行时，一次 hasNext() 可能跳过多行。但从整个迭代过程看，每一行最多被跳过一次，每个元素最多被访问一次。因此所有调用加起来总时间是 O(N + V)。所以 next() / hasNext() 的 均摊时间复杂度 可以认为是 O(1)。- 空间复杂度：
O(1)
因为只使用两个指针，没有复制元素。
总结
这两种写法的区别，本质上是 eager vs lazy。
如果只是为了快速写出可用代码，flatten 版本最简单。
双指针 + forward()版本体现了 iterator 的本质：
不提前复制全部数据，只保存当前遍历位置，按需推进。
- 作者:Fan Luo
- 链接:https://fanluo.me/article/leetcode-251-展开二维向量
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
上一篇
[Leetcode 240] 搜索二维矩阵 II
下一篇
[Leetcode 300] 最长递增子序列