LC 284. 顶端迭代器

题目描述

这是 LeetCode 上的 284. 顶端迭代器 ，难度为 中等。

请你设计一个迭代器，除了支持 hasNext 和 next 操作外，还支持 peek 操作。

实现 PeekingIterator 类：

• PeekingIterator(int[] nums) 使用指定整数数组 nums 初始化迭代器。
• int next() 返回数组中的下一个元素，并将指针移动到下个元素处。
• bool hasNext() 如果数组中存在下一个元素，返回 true ；否则，返回 false。
• int peek() 返回数组中的下一个元素，但 不 移动指针。

示例：

输入：
["PeekingIterator", "next", "peek", "next", "next", "hasNext"]
[[[1, 2, 3]], [], [], [], [], []]

输出：
[null, 1, 2, 2, 3, false]

解释：
PeekingIterator peekingIterator = new PeekingIterator([1, 2, 3]); // [1,2,3]
peekingIterator.next();    // 返回 1 ，指针移动到下一个元素 [1,2,3]
peekingIterator.peek();    // 返回 2 ，指针未发生移动 [1,2,3]
peekingIterator.next();    // 返回 2 ，指针移动到下一个元素 [1,2,3]
peekingIterator.next();    // 返回 3 ，指针移动到下一个元素 [1,2,3]
peekingIterator.hasNext(); // 返回 False

提示：

• $1 <= nums.length <= 1000$
• $1 <= nums[i] <= 1000$
• 对 next 和 peek 的调用均有效
• next、hasNext 和 peek 最多调用 $1000$ 次

进阶：你将如何拓展你的设计？使之变得通用化，从而适应所有的类型，而不只是整数型？

---

迭代器基本认识 + 模拟

常规的迭代器的「访问」只支持两种操作：

• hasNext() 操作：如果存在下一元素，返回 True，否则返回 False。实现上，就是判断游标是否到达结尾位置；
• next() 操作：返回下一元素（当不存在下一元素时，返回 null）。实现上，就是返回游标指向的元素，并让游标后移。

在本题，还需要我们额外支持 peek() 操作，即在移动游标的前提下，返回游标指向的元素。

实现上，我们可以让操作提前一步进行，事先调用一次 next() 并使用该变量 $next$ 存起该元素，通过外部调用 peek() 还是 next() 来决定是否要更新 $next$；同时由于我们事先存起了下一访问位置的元素，我们可以通过判断 $next$ 是否为 null 来得知是否到达迭代器结尾（hasNext() 实现）。

代码：

class PeekingIterator implements Iterator<Integer> {
    Iterator<Integer> iter;
    Integer next;
	public PeekingIterator(Iterator<Integer> iterator) {
        iter = iterator;
        if (iter.hasNext()) next = iter.next();
	}
	
	public Integer peek() {
        return next;
	}
	
	@Override
	public Integer next() {
        Integer ans = next;
        next = iter.hasNext() ? iter.next() : null;
	    return ans;
	}
	
	@Override
	public boolean hasNext() {
        return next != null;
	}
}

• 时间复杂度：$O(1)$
• 空间复杂度：$O(1)$

---

进阶

• 你将如何拓展你的设计？使之变得通用化，从而适应所有的类型，而不只是整数型？

得益于 Java 的「泛型」设计，我们可以很轻松地支持任意类型：只需要将 Integer 修改成代指泛型的标识即可，例如 E。

代码：

class PeekingIterator implements Iterator<E> {
    Iterator<E> iter;
    E next;
	public PeekingIterator(Iterator<E> iterator) {
        iter = iterator;
        if (iter.hasNext()) next = iter.next();
	}
	
	public E peek() {
        return next;
	}
	
	@Override
	public E next() {
        E ans = next;
        next = iter.hasNext() ? iter.next() : null;
	    return ans;
	}
	
	@Override
	public boolean hasNext() {
        return next != null;
	}
}

Java 的泛型实现原理是「擦除法」。即实际上，都是以 Object 的顶层类型来存储，只不过在编译期，编译器会自动增加强制类型转换的代码，而在增加了强制类型转换的逻辑后，泛型信息也就不再需要，于是在编译过后，泛型信息会被直接擦除，而不会带到运行时。

其他不支持「泛型」的语言，可以采用类似的思路来实现：保存一个数据类型，在实现使用到泛型的接口时，先手动强转一下，再接收进来/返回出去。

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.284 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。