284. 窥视迭代器

🟠   🔖  设计 数组 迭代器  🔗 力扣 LeetCode

题目

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() 返回数组中的下一个元素，但 不 移动指针。

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

示例 1：

输入：

["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 次

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

解题思路

PeekingIterator 是对一个迭代器进行包装，提供额外的 peek() 功能，用于预览下一个元素而不移动迭代器的当前位置。实现过程中，需要维护一个缓存变量来存储“预览的值”，以便在调用 peek() 后，实际调用 next() 时返回正确的结果。

1. 缓存机制

   • 引入一个私有变量 peeked 用于存储调用 peek() 时预览的值。
   • 如果 peeked 中有值，说明上一次调用了 peek() 而未调用 next()，这时应直接返回缓存值。

2. 三个方法的逻辑

   • peek()
     • 如果 peeked 中有值，直接返回该值。
     • 如果 peeked 中为空，调用 iterator.next() 获取下一个值并存入 peeked，然后返回该值。
   • next()
     • 如果 peeked 中有值，说明调用过 peek()，返回缓存值并清空 peeked。
     • 如果 peeked 为空，直接调用 iterator.next() 返回下一个值。
   • hasNext()
     • 如果 peeked 中有值，说明还有预览的元素，返回 true。
     • 如果 peeked 为空，则调用 iterator.hasNext() 判断底层迭代器是否有更多元素。

3. 边界条件

   • peeked 的初始值为 null，以便区分缓存状态。
   • 处理 iterator 在边界条件（如没有更多元素时）的行为。

复杂度分析

• 时间复杂度：O(1)，peek()、next() 和 hasNext() 的时间复杂度均为 O(1)，因为每次操作最多涉及缓存或底层迭代器的调用。
• 空间复杂度：O(1)，额外的缓存变量 peeked 占用常数空间。

代码

class PeekingIterator {
	constructor(iterator) {
		this.iterator = iterator; // 底层迭代器
		this.peeked = null; // 缓存的预览值
	}

	peek() {
		// 如果没有缓存值，获取下一个值并缓存
		if (this.peeked === null) {
			this.peeked = this.iterator.next();
		}
		return this.peeked;
	}

	next() {
		// 如果缓存中有值，返回缓存值并清空缓存
		if (this.peeked !== null) {
			const temp = this.peeked;
			this.peeked = null;
			return temp;
		}
		// 如果没有缓存，直接从底层迭代器获取下一个值
		return this.iterator.next();
	}

	hasNext() {
		// 如果缓存中有值，则一定有下一个元素
		if (this.peeked !== null) {
			return true;
		}
		// 否则检查底层迭代器是否有更多元素
		return this.iterator.hasNext();
	}
}

相关题目

题号	标题	题解	标签	难度	力扣
173	二叉搜索树迭代器	[✓]	栈 树 设计 3+	🟠	🀄️ 🔗
251	展开二维向量 🔒		设计 数组 双指针 1+	🟠	🀄️ 🔗
281	锯齿迭代器 🔒		设计 队列 数组 1+	🟠	🀄️ 🔗