LeetCode 251. 展开二维向量
题目描述
题意分析
为二维向量实现按行顺序读取的迭代器：先遍历第一行的所有元素，再遍历后续各行。行可以为空，各行长度也不必相同。
next返回并消费下一个元素，hasNext只判断是否还有元素，可以连续调用多次而不改变下一次应返回的值。沿用本篇已有调用约定，next只在仍有下一项时调用。
解法：行列游标跳过空行
核心思路
[!blue]
不必预先把全部元素复制到一维数组。保存原向量引用，再用行游标
i、列游标j表示下一个待处理位置；当前行读完后，继续到下一行开头即可。游标可能停在空行或刚被耗尽的行上，所以先由公共函数
forward整理位置：只要i还在范围内，而且j已经达到当前行长度，就让i前进并将j重置为0。连续空行也要反复跳过，直到遇到真实元素或走完整个向量。整理后有且只有两种情况：
i仍有效，此时(i, j)就是下一元素；或i等于总行数，表示全部结束。hasNext只执行这种整理并判断行游标，不跨过任何真实元素，因此重复查询仍指向同一个值。
next也先调用forward，保证不依赖调用方一定先做一次查询。随后读取当前位置，并且只让列游标加一，真正消费一个元素。下次调用再统一处理可能出现的行结束。
解题步骤
- 构造时保存二维向量引用，将行列游标初始化为
0。- 公共整理函数用循环跳过已经耗尽的行，每进入新行都把列游标归零。
hasNext先整理，再判断i是否小于总行数。next先整理，再返回vec[i][j]并将j增加一。
代码实现
class Vector2D {
private int i;
private int j;
private int[][] vec;
public Vector2D(int[][] vec) {
this.vec = vec;
}
public int next() {
forward();
return vec[i][j++];
}
public boolean hasNext() {
forward();
return i < vec.length;
}
private void forward() {
while (i < vec.length && j >= vec[i].length) {
++i;
j = 0;
}
}
}
type Vector2D struct {
i, j int
vec [][]int
}
func Constructor(vec [][]int) Vector2D {
return Vector2D{vec: vec}
}
func (this *Vector2D) Next() int {
this.forward()
answer := this.vec[this.i][this.j]
this.j++
return answer
}
func (this *Vector2D) HasNext() bool {
this.forward()
return this.i < len(this.vec)
}
func (this *Vector2D) forward() {
for this.i < len(this.vec) && this.j >= len(this.vec[this.i]) {
this.i++
this.j = 0
}
}
复杂度分析
设二维向量有
m行，共发生q次迭代器调用。
- 时间复杂度：构造为 $O(1)$；行游标在全部调用中最多前进
m次，其余每次调用只做常数工作，所以总时间为 $O(m+q)$。单次调用可能跨过很多空行，最坏为 $O(m)$，不能在空行很多而调用很少时直接声称每次都是常数时间。- 空间复杂度：$O(1)$ 额外空间，只保存原向量引用和两个游标，没有复制全部元素。
关键点总结
[!green]
- 整理游标只跳过不存在的元素位置，消费元素只由
next的列游标递增完成。- 两个接口共用同一个整理过程，避免空行与行结束逻辑不一致。
- 行游标只前进不回退，空行扫描的成本在全部调用中只发生一次。
易错点总结
[!yellow]
- 用
if只跳过一行，无法处理连续空行，必须循环直到位置有效或整体结束。- 切换行后不把
j归零，会跳过下一行开头的元素，甚至直接误判该行耗尽。hasNext也让列游标越过元素，会使重复查询丢数据。- 只检查当前行是否还有元素，会忽略后续仍然非空的行。
next不整理位置而完全依赖之前的查询，调用间跨行时就容易读到无效下标。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 341. 扁平化嵌套列表迭代器 | 中等 | 同样延迟展开并让 hasNext 准备下一项，原题存在任意嵌套，本题只有两层游标。 |
| 173. 二叉搜索树迭代器 | 中等 | 同样把遍历封装为 next 与 hasNext，本题只需行列游标，BST 迭代器需要保存下降路径。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！