LeetCode 251. 展开二维向量

2026-03-28 HGNULB 约 9 分钟

文章信息 2 个分类 4 个标签

分类

LeetCode 中等

题目描述

✅ 251. 展开二维向量

题意分析

题目目标：给一个二维数组，实现迭代器接口 next() 与 hasNext()，按行优先顺序逐个吐出所有元素。

核心约束：这是设计题，判分点不在「能不能把元素取出来」，而在空间与调用节奏。把二维数组整个拍平成一维列表再返回下标，功能上完全正确，但它在构造时就吃掉了 $O(总元素数)$ 的额外空间，也放弃了迭代器「按需产出」的语义——面试官问这题就是想看你会不会只用两个下标做到 $O(1)$ 额外空间。另一条关键约束是内层数组可以为空，而且可以连着好几个都为空，甚至整个二维数组的所有行都是空的。

边界处理：外层为空；某些行为空且出现在开头、中间或结尾；连续多个空行；hasNext() 被连续调用多次不应产生副作用；next() 与 hasNext() 的调用顺序任意（题目保证 next() 只在有元素时被调用，但代码不能因为多调一次 hasNext() 就乱掉）。

实现取舍：拍平法 $O(N)$ 空间、构造 $O(N)$ 时间；双下标法 $O(1)$ 空间、构造 $O(1)$ 时间，代价是要把「跳过空行」这件事处理干净。后者是标准答案。

解法：双指针收缩边界

核心思路

先说拍平法为什么不够。把所有元素复制进一个 List 再用一个游标遍历，代码三行就能写完，但它有两个硬伤：一是额外空间与数据规模同阶，二是即便调用方只取前两个元素，构造函数也已经把整个数据集扫完了。迭代器的价值恰恰是「不预先物化」，所以正确的方向是——只记录位置，不复制数据。

位置需要两个维度：行号 i 与列号 j。于是状态定义为：(i, j) 指向下一个待返回的元素。这个定义看似自然，但直接维护它会遇到麻烦：next() 返回元素后 j 自增，此时 j 可能已经越过本行末尾，(i, j) 就不再是一个合法坐标了；而下一行还可能是空行，需要连续跳好几次。

破解的办法是放宽不变量：允许 (i, j) 处于「尚未规范化」的中间状态，但保证在每次对外可见的操作之前先把它规范化。规范化动作 forward() 做的事很简单——只要当前行已经走到头（j >= vec[i].length），就换到下一行并把 j 归零，用 while 而不是 if，这样连续的空行会被一口气跳完。

于是最终的不变量是：forward() 执行完毕后，要么 i == vec.length（数据已耗尽），要么 (i, j) 指向一个真实存在的元素。hasNext() 先规范化再判断 i < vec.length，next() 先规范化再返回 vec[i][j++]——两个方法都以 forward() 开头，这是它们能任意交错调用而不出错的根本原因。

还有一点值得注意：forward() 是幂等的。已经规范化的状态再规范化一次，while 的条件立刻为假，什么也不会发生。所以连续调用十次 hasNext() 与调用一次的效果完全相同，不会「吃掉」任何元素。

解题步骤

第一步：构造函数只保存二维数组的引用，i、j 默认为 0。 为什么不在这里做任何扫描：迭代器的构造应当是 $O(1)$ 的，把「跳过开头的空行」这件事推迟到第一次 hasNext()/next() 时由 forward() 顺手完成，代码反而更少。

第二步：写规范化方法 forward()，循环条件是 i < vec.length && j >= vec[i].length。 为什么两个条件缺一不可：i < vec.length 防止越界访问 vec[i]，j >= vec[i].length 判断当前行是否已耗尽。为什么进入循环体后是 ++i 且 j = 0：换行必须把列号重置，否则会带着上一行的列号去访问新行。为什么用 while 不用 if：连续空行时一次跳跃不够，必须一直跳到有元素的行或者跳出数据末尾。

第三步：hasNext() 先调用 forward()，再返回 i < vec.length。 为什么必须先规范化：不规范化的话，当 (i, j) 停在某个已耗尽行的末尾时，i 仍小于 vec.length，会错误地报告「还有元素」。

第四步：next() 先调用 forward()，再返回 vec[i][j++]。 为什么这里也要规范化：调用方可能不先问 hasNext() 就直接 next()，此时 (i, j) 可能还停在上一行的末尾；先规范化才能保证读到的是正确的下一个元素。为什么用 j++ 后缀自增：先取当前值作为返回结果，再把游标推进一格，恰好是迭代器的语义。

以 vec = [[1, 2], [3], [4]] 走一遍：构造后 i = 0、j = 0。

第一次 next()：forward() 检查 j = 0 < vec[0].length = 2，条件不成立，不做任何事；返回 vec[0][0] = 1，j 变成 1。

第二次 next()：forward() 检查 j = 1 < 2，不动；返回 vec[0][1] = 2，j 变成 2。此时 (0, 2) 已经越界，进入了「未规范化」的中间状态——这是被允许的，因为下一次对外操作会先修好它。

调用 hasNext()：forward() 发现 i = 0 < 3 且 j = 2 >= 2，于是 i 变成 1、j 归零；再检查 j = 0 < vec[1].length = 1，循环结束。规范化完成，(1, 0) 指向真实元素 3。返回 1 < 3 即 true。

第三次 next()：forward() 无事可做（状态已规范）；返回 vec[1][0] = 3，j 变成 1。

第四次 next()：forward() 发现 j = 1 >= vec[1].length = 1，i 变成 2、j 归零，检查 j = 0 < vec[2].length = 1 退出；返回 vec[2][0] = 4，j 变成 1。

再调用 hasNext()：forward() 发现 j = 1 >= vec[2].length = 1，i 变成 3、j 归零；此时 i = 3 不再小于 vec.length = 3，循环因第一个条件失败而退出——注意这里如果没有 i < vec.length 这个守卫，vec[3].length 会直接越界。返回 3 < 3 即 false，遍历结束。输出序列 1, 2, 3, 4，与期望一致。

再以 vec = [[], [], [1], []] 验证空行处理：构造后 (0, 0)。调用 hasNext()：forward() 中 j = 0 >= vec[0].length = 0 成立，跳到 (1, 0)；仍有 0 >= 0，跳到 (2, 0)；此时 0 < 1，退出循环，返回 true。next() 返回 1，j 变成 1。再 hasNext()：j = 1 >= 1 跳到 (3, 0)，0 >= 0 再跳到 (4, 0)，i = 4 不小于 4 退出，返回 false。开头两个空行和结尾一个空行都被 while 一次性吞掉，这就是不能写 if 的现场证据。

代码实现

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
    }
}

复杂度分析

时间复杂度：构造 $O(1)$，next() 与 hasNext() 均摊 $O(1)$。凭什么：forward() 里 i 只增不减，整个生命周期中它最多推进 $m$ 次（$m$ 为行数），这部分开销被分摊到全部调用上；单次调用最坏是 $O(m)$（连续跳过大量空行），但总量有界，因此均摊后是常数。

空间复杂度：$O(1)$。凭什么：只额外保存 i、j 两个整型和一份对原数组的引用，没有复制任何元素，这正是它优于「构造时拍平成一维列表」的地方。

关键点总结

迭代器设计题的评分点是「不预先物化 + 额外空间常数」，功能正确只是及格线。 上来就拍平会被认为没抓住题意。

把「规范化」抽成一个独立的私有方法，并让每个公开方法都以它开头。 这一条模式让 next() 与 hasNext() 可以任意顺序、任意次数交错调用而互不干扰，是所有多状态迭代器的通用骨架。

允许内部状态短暂不合法，只要求在对外可见的边界上合法。 这个思路比「每次操作后立刻修复」更简单——后者要在 next() 末尾也写一遍跳行逻辑，重复且容易漏。

规范化必须幂等。 幂等保证了重复调用 hasNext() 不会吃掉元素，这是迭代器契约的一部分，也是面试官爱设的陷阱。

跳过空容器要用 while 而不是 if，并把越界守卫写在条件的最左边。 短路求值的顺序在这里是正确性的一部分，写反了会越界访问。

面试视角：先主动否定拍平法并说明理由（空间、惰性），再给双下标 + forward() 的写法，然后自己举出「连续空行」「先调 next() 不调 hasNext()」「连调多次 hasNext()」三个测试点来证明设计的健壮性。如果面试官追加 remove() 接口，说明需要额外记录「上一次返回的位置」以及删除后 j 的回退处理，这是很自然的延伸。

易错点总结

错误写法：forward() 用 if 而不是 while → 用例 [[], [], [1]]，第一次 hasNext() 只跳过一个空行停在 (1, 0)，返回 true，随后 next() 访问 vec[1][0] 越界。

错误写法：forward() 的条件写成 j >= vec[i].length && i < vec.length（顺序反了） → 用例 [[1]]，取完元素后 j = 1、i = 0，下一次 hasNext() 先跳到 i = 1，再判断 vec[1].length 时越界抛异常。

错误写法：换行时忘记 j = 0 → 用例 [[1, 2], [3]]，取完第一行后 j = 2，跳到第 1 行时 j 仍是 2，forward() 认为第 1 行也已耗尽，直接跳到 i = 2，元素 3 被跳过，hasNext() 返回 false。

错误写法：只在 hasNext() 里调 forward()，next() 不调 → 用例 [[1], [2]]，调用方连续两次 next() 而不问 hasNext()，第二次时 (0, 1) 未规范化，vec[0][1] 越界。

错误写法：只在 next() 里调 forward()，hasNext() 直接返回 i < vec.length → 用例 [[1], []]，取完元素 1 后 (0, 1)，hasNext() 看到 i = 0 < 2 返回 true，但实际已无元素，调用方再调 next() 会拿到越界或错误结果。

错误写法：hasNext() 里除了 forward() 还顺手推进了 j → 破坏幂等性，用例 [[1, 2]] 中连续调用两次 hasNext() 会让元素 1 被跳过，第一次 next() 直接返回 2。

错误写法：next() 写成 return vec[i++][j] 或先自增 i → 用例 [[1, 2]]，第一次调用后 i 变成 1 而 j 仍是 0，第二次 forward() 时 vec[1] 越界。

错误写法：构造函数里就把所有元素复制进 List → 用例是一个 $10^5 \times 10^5$ 的稀疏二维数组时内存爆炸；功能虽对，但违背了题目考察的惰性求值意图。

错误写法：用「元素总数 - 已返回数」来实现 hasNext() → 需要在构造时遍历统计总数，退回 $O(总行数)$ 的构造开销，且一旦外部修改了原数组，计数与实际不符。

错误写法：认为空的外层数组需要特判 → 用例 []，forward() 中 i = 0 不小于 vec.length = 0，循环直接不进入，hasNext() 返回 false，本就正确；额外的特判反而增加出错面。

相似题目

题目	难度	考察点
173. 二叉搜索树迭代器	中等	底层是树而非数组，需要用显式栈把中序遍历拆成可暂停的状态
281. 锯齿迭代器	中等	输出顺序在多个列表间轮转，状态里要多存一个「当前轮到谁」
341. 扁平化嵌套列表迭代器	中等	嵌套深度不固定，两个下标不够用，必须改成栈来保存任意层级的位置