原文链接: https://leetcode-cn.com/problems/peeking-iterator

英文原文

Design an iterator that supports the peek operation on an existing iterator in addition to the hasNext and the next operations.

Implement the PeekingIterator class:

• PeekingIterator(Iterator<int> nums) Initializes the object with the given integer iterator iterator.
• int next() Returns the next element in the array and moves the pointer to the next element.
• boolean hasNext() Returns true if there are still elements in the array.
• int peek() Returns the next element in the array without moving the pointer.

Note: Each language may have a different implementation of the constructor and Iterator, but they all support the int next() and boolean hasNext() functions.

 

Example 1:

Input
["PeekingIterator", "next", "peek", "next", "next", "hasNext"]
[[[1, 2, 3]], [], [], [], [], []]
Output
[null, 1, 2, 2, 3, false]

Explanation
PeekingIterator peekingIterator = new PeekingIterator([1, 2, 3]); // [1,2,3]
peekingIterator.next();    // return 1, the pointer moves to the next element [1,2,3].
peekingIterator.peek();    // return 2, the pointer does not move [1,2,3].
peekingIterator.next();    // return 2, the pointer moves to the next element [1,2,3]
peekingIterator.next();    // return 3, the pointer moves to the next element [1,2,3]
peekingIterator.hasNext(); // return False

 

Constraints:

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 1000
• All the calls to next and peek are valid.
• At most 1000 calls will be made to next, hasNext, and peek.

 

Follow up: How would you extend your design to be generic and work with all types, not just integer?

中文题目

请你在设计一个迭代器，在集成现有迭代器拥有的 hasNext 和 next 操作的基础上，还额外支持 peek 操作。

实现 PeekingIterator 类：

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

注意：每种语言可能有不同的构造函数和迭代器，但均支持 int next() 和 boolean hasNext() 函数。

 

示例：

输入：
["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 的顶层类型来存储，只不过在编译期，编译器会自动增加强制类型转换的代码，而在增加了强制类型转换的逻辑后，泛型信息也就不再需要，于是在编译过后，泛型信息会被直接擦除，而不会带到运行时。

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

---

最后

如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ (“▔□▔)/

也欢迎你 关注我（公主号后台回复「送书」即可参与长期看题解学算法送实体书活动）或 加入「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。

所有题解已经加入 刷题指南，欢迎 star 哦 ~

统计信息

通过次数	提交次数	AC比率
25729	33383	77.1%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
二叉搜索树迭代器	中等
展开二维向量	中等
锯齿迭代器	中等