LeetCode 281. 锯齿迭代器
目录
题目描述
题意分析
给两个整数列表
v1、v2，设计一个迭代器类，交替返回它们的元素：先v1[0]，再v2[0]，再v1[1]，再v2[1]……某个列表提前耗尽后，剩下的元素按原顺序依次输出。需要实现next()和hasNext()两个方法。「设计迭代器」这四个字规定了接口形态，也规定了性能预期：
next()和hasNext()都应当是 $O(1)$ 的，而且构造函数不应该把所有元素预先拉平——迭代器的意义就在于按需产出，调用方可能只取前几个就丢弃。这一点是本题与「合并两个数组」的本质区别。更重要的信号在进阶要求里：如果不是两个列表而是
k个列表，代码能不能不加修改地扩展？这句话直接否定了「用一个布尔标志在两个列表之间来回切换」的写法——那种写法在k = 2时能过，但一旦推广到k个就要推倒重来。所以从一开始就该按「任意多个列表」来设计，k = 2只是它的一个实例。「交替」这个规则在某个列表耗尽后要退化成什么样，题目给的样例说清楚了：
v1 = [1,2]、v2 = [3,4,5,6]的输出是[1,3,2,4,5,6]，也就是v1用完之后剩下的5,6连续输出，中间不会有空洞或跳过。换句话说，耗尽的列表要从轮转序列中彻底退出，而不是留在序列里被反复跳过。边界：某个列表初始就为空时，从第一次
next()起就只输出另一个列表；两个都为空时hasNext()必须一开始就返回false；题目保证调用方在hasNext()为真时才调next()，但把这个前提说清楚仍是设计题该做的事。
解法：队列存储索引
核心思路
锯齿顺序本质是对所有尚未耗尽的列表做轮转。队列中只保存每个活跃列表的一个游标
(listIndex, elementIndex)：取出队首元素后，若该列表还有下一个元素，就把后继游标放回队尾；否则该列表自然退出轮转。构造时只把非空列表的首游标按输入顺序入队。状态不变量是：队列中每个游标都指向一个合法未读元素，且队列顺序就是后续各列表获得读取机会的顺序。
hasNext()因而等价于队列非空；next()只需一次出队、一次读取和至多一次入队。使用真正的队列可以让耗尽列表自动消失，也能直接推广到多个列表。正确性说明：队首游标代表当前轮最早应输出的元素。将同一列表的后继放到队尾，保证其他活跃列表各获得一次机会后才再次轮到它；没有后继时不再入队，保证不会越界。由构造顺序归纳，输出恰好按锯齿顺序覆盖所有元素一次。
解题步骤
- 保存两个原列表的引用，不预先复制元素。
- 按
v1、v2顺序把非空列表的(index,0)游标加入队列。next()弹出队首游标并读取其元素。- 若同一列表仍有后继，将新游标加入队尾。
hasNext()直接判断队列是否为空。
v1=[1,2]、v2=[3,4,5,6]输出[1,3,2,4,5,6]；v1=[]时队列表只包含 v2，第一次就从 v2 读取；两个列表都为空时hasNext()立即为假。
代码实现
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
public class ZigzagIterator {
private final List<List<Integer>> lists = new ArrayList<>(2);
private final Queue<int[]> queue = new ArrayDeque<>();
public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
lists.add(v1);
lists.add(v2);
for (int i = 0; i < lists.size(); i++) {
if (!lists.get(i).isEmpty()) {
queue.offer(new int[] {i, 0});
}
}
}
public int next() {
int[] cursor = queue.poll();
int value = lists.get(cursor[0]).get(cursor[1]);
if (cursor[1] + 1 < lists.get(cursor[0]).size()) {
queue.offer(new int[] {cursor[0], cursor[1] + 1});
}
return value;
}
public boolean hasNext() {
return !queue.isEmpty();
}
}
import "container/list"
type cursor struct {
listIndex int
elementIndex int
}
type ZigzagIterator struct {
lists [][]int
queue *list.List
}
func Constructor(v1 []int, v2 []int) *ZigzagIterator {
iterator := &ZigzagIterator{
lists: [][]int{v1, v2},
queue: list.New(),
}
for index, values := range iterator.lists {
if len(values) > 0 {
iterator.queue.PushBack(cursor{listIndex: index})
}
}
return iterator
}
func (iterator *ZigzagIterator) Next() int {
front := iterator.queue.Front()
current := front.Value.(cursor)
iterator.queue.Remove(front)
value := iterator.lists[current.listIndex][current.elementIndex]
current.elementIndex++
if current.elementIndex < len(iterator.lists[current.listIndex]) {
iterator.queue.PushBack(current)
}
return value
}
func (iterator *ZigzagIterator) HasNext() bool {
return iterator.queue.Len() > 0
}
复杂度分析
- 构造时间：$O(k)$，其中本题 $k=2$；
next()与hasNext()均为 $O(1)$。- 空间复杂度：$O(k)$。每个未耗尽列表在队列中最多有一个游标，不复制原元素。
关键点总结
- “轮流处理且完成者退出”是队列调度的直接信号。
- 队列只保存合法未读游标，使
hasNext()能退化为一次空判断。- 后继必须放队尾；放队首会连续读完同一列表。
- 构造只保存引用和首游标，保持迭代器的惰性。
- Go 的公开接口方法需命名为
Next、HasNext，并使用真正的队列维持 $O(1)$ 出队。
易错点总结
- 把空列表游标入队：第一次读取就会下标越界。
- 无条件放回后继游标：列表耗尽后
hasNext()仍返回真，下一次读取越界。- 后继放到队首：
[1,2]与[3,4]会输出[1,2,3,4]而非交替序列。- 初始入队顺序反转：第一轮会从 v2 开始。
- 构造时拉平全部元素：失去惰性并把额外空间增至 $O(N)$。
- Go 用
queue = queue[1:]后持续 append：广义 k 列表下可能反复扩容复制，不能保证单步与额外空间严格为 $O(1)$、$O(k)$。- Go 方法写成小写
next/hasNext：不符合题目生成器调用的导出方法名，会编译失败。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 251. 展开二维向量 | 中等 | 顺序拉平而非交替，考察 hasNext() 里跳过空行的惰性推进 |
| 341. 扁平化嵌套列表迭代器 | 中等 | 嵌套结构需要用栈做深度优先展开，与本题的队列轮转形成对照 |
| 173. 二叉搜索树迭代器 | 中等 | 用栈保存左链把中序遍历改造成惰性迭代，同样要求 $O(1)$ 摊还与 $O(h)$ 空间 |
| 232. 用栈实现队列 | 简单 | 设计题的摊还分析入门，考察怎样论证单次操作的摊还 $O(1)$ |
| 703. 数据流中的第 K 大元素 | 简单 | 同为流式设计，但调度依据是元素大小，结构换成固定容量的小顶堆 |
| 295. 数据流的中位数 | 困难 | 双堆维持平衡的流式设计，重点在两个容器之间的再平衡时机 |
| 146. LRU 缓存 | 中等 | 同样要求所有接口 $O(1)$，靠哈希表加双向链表组合，考察结构选型的推导过程 |
| 380. O(1) 时间插入、删除和获取随机元素 | 中等 | 用「数组 + 下标映射」满足三个 $O(1)$ 接口，练习为契约反推数据结构 |