LeetCode 281. 锯齿迭代器
题目描述
题意分析
设计一个迭代器，轮流读取两个列表的下一个元素。某个列表耗尽后，继续按顺序读取另一个列表的剩余元素。
next返回并消耗下一项，hasNext只回答是否还有下一项。读取按调用逐步发生，不需要在构造时提前生成完整的交替序列。
解法：队列游标轮转
核心思路
[!blue]
用队列安排下一次轮到哪个列表。每个尚未耗尽的列表在队列中恰好保存一个游标，游标包含列表编号和该列表下一未读元素的下标。列表内部顺序由下标保证，列表之间的轮流顺序由队列保证。
初始化时按第一个、第二个列表的顺序，把非空列表的首游标加入队列。每次调用
next，取出队首游标并读取它指向的元素，然后将该列表的下标推进一位。如果还有元素，就把后继游标放到队尾；已经耗尽则不再放回。放到队尾后，其他活跃列表会先各获得一次读取机会，这就实现了轮流取值。当只剩一个列表时，它取出后又回到唯一的队列位置，自然连续输出剩余元素，不需要另外切换处理方式。
队列中没有无效游标，因此“队列非空”等价于“还有未读元素”。
hasNext只检查队列，不移除或推进游标，连续检查也不会跳过数据。调用next前应确认存在下一项。实现只保存原列表引用和活跃游标，没有预先复制全部元素，也不会因为另一个列表较短而丢掉较长列表的尾部。
解题步骤
- 保存两个列表，按输入顺序将非空列表的首游标加入队列。
next弹出队首，读取对应列表的当前下标元素。- 若该列表还有后继元素，将后继游标加入队尾；否则让它退出轮转。
- 返回刚读出的值。
hasNext始终只判断队列是否非空。
代码实现
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
}
进阶：推广到 k 个列表
将输入推广为
k个列表时，只需让构造函数保存这k个列表，并按给定顺序，把每个非空列表的首游标加入队列。next和hasNext的逻辑不依赖列表总数，可以直接沿用。队首读一项、有后继就排到队尾，让所有仍有元素的列表按原顺序循环取值。空列表从一开始就被跳过，耗尽的列表在读取最后一项后退出，每个活跃列表始终只有一个游标。
初始化需要扫描
k个列表，时间为 $O(k)$；支持常数时间下标访问时，每次读取和判断仍为 $O(1)$，辅助空间为 $O(k)$。若共有N个元素，完整遍历的总时间为 $O(N+k)$，不用预先存下这N个输出元素。
复杂度分析
- 时间复杂度：本题只有两个列表，构造和
hasNext均为 $O(1)$。在输入支持常数时间下标访问的前提下，next只进行一次读取和常数次队列操作，为 $O(1)$。- 空间复杂度：$O(1)$，本题至多保存两个活跃游标和两个列表引用，不复制列表元素。
关键点总结
[!green]
- 每个活跃列表恰有一个游标，队首代表下一次读取机会。
- 读完一项后把后继放到队尾，实现列表之间的公平轮转。
- 耗尽的列表不再入队，所以队列是否为空就能准确回答
hasNext。- 同一轮转逻辑适用于任意数量的列表，变化只在初始化的列表集合。
易错点总结
[!yellow]
- 空列表也建立游标：第一次读取它时就会访问不存在的元素。
- 列表耗尽后仍把游标放回：队列中出现无效位置，
hasNext也会误判。- 把后继放回队首：会连续读取同一个列表，失去轮流取值的顺序。
- 在
hasNext中推进游标：只检查是否有下一项也会消耗数据。- 只处理两个列表的公共长度：较长列表仍有剩余元素，必须继续读取直到所有游标都退出。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 251. 展开二维向量 | 中等 | 同样把多行容器封装为迭代器，原题逐行连续输出，本题在多条序列间轮流取下一项。 |