Medium

题目描述

设计一个迭代器，在现有迭代器的基础上支持预览操作，同时保持 hasNext 和 next 操作。

实现 PeekingIterator 类：

  • PeekingIterator(Iterator<int> nums) 用给定的整数迭代器初始化对象。
  • int next() 返回数组中的下一个元素并将指针移动到下一个元素。
  • boolean hasNext() 如果数组中仍有元素，则返回 true。
  • int peek() 返回数组中的下一个元素但不移动指针。

注意：每种语言可能有不同的构造函数和迭代器实现，但都支持 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 次

进阶： 如何扩展你的设计使其通用化，适用于所有类型而不仅仅是整数？

解题思路

这是一个经典的设计题，核心思想是缓存下一个元素来实现 peek 功能。

主要思路有两种：

方法一：预读缓存（推荐）

  • 维护一个 nextVal 变量和一个 hasNextVal 标志
  • 在初始化或每次调用 next() 后，如果原迭代器还有元素，就预读下一个元素并缓存
  • peek() 直接返回缓存的值，不改变状态
  • hasNext() 检查是否有缓存的值
  • next() 返回缓存的值，然后尝试预读下一个元素

这种方法的优点是逻辑清晰，每次操作的时间复杂度都是 O(1)。

方法二：懒加载缓存

  • 只在需要时才缓存下一个元素
  • 维护一个 peekedValue 和 hasPeeked 标志
  • 第一次调用 peek() 时才从原迭代器读取并缓存
  • next() 时优先返回缓存值，否则从原迭代器读取

两种方法都能正确实现功能，但方法一在初始化时就建立了一致的状态，更容易理解和维护。关键是要确保不会重复读取原迭代器的同一个元素，也不会跳过任何元素。

代码实现

class PeekingIterator : public Iterator {
private:
    int nextVal;
    bool hasNextVal;
    
public:
    PeekingIterator(const vector<int>& nums) : Iterator(nums) {
        if (Iterator::hasNext()) {
            nextVal = Iterator::next();
            hasNextVal = true;
        } else {
            hasNextVal = false;
        }
    }
    
    int peek() {
        return nextVal;
    }
    
    int next() {
        int result = nextVal;
        if (Iterator::hasNext()) {
            nextVal = Iterator::next();
            hasNextVal = true;
        } else {
            hasNextVal = false;
        }
        return result;
    }
    
    bool hasNext() const {
        return hasNextVal;
    }
};

class PeekingIterator:
    def __init__(self, iterator):
        self.iterator = iterator
        self.has_next_val = self.iterator.hasNext()
        self.next_val = self.iterator.next() if self.has_next_val else None

    def peek(self):
        return self.next_val

    def next(self):
        result = self.next_val
        self.has_next_val = self.iterator.hasNext()
        self.next_val = self.iterator.next() if self.has_next_val else None
        return result

    def hasNext(self):
        return self.has_next_val

class PeekingIterator {
    private IEnumerator<int> iterator;
    private int nextVal;
    private bool hasNextVal;
    
    public PeekingIterator(IEnumerator<int> iterator) {
        this.iterator = iterator;
        hasNextVal = iterator.MoveNext();
        if (hasNextVal) {
            nextVal = iterator.Current;
        }
    }
    
    public int Peek() {
        return nextVal;
    }
    
    public int Next() {
        int result = nextVal;
        hasNextVal = iterator.MoveNext();
        if (hasNextVal) {
            nextVal = iterator.Current;
        }
        return result;
    }
    
    public bool HasNext() {
        return hasNextVal;
    }
}

var PeekingIterator = function(iterator) {
    this.iterator = iterator;
    this.hasNextVal = this.iterator.hasNext();
    this.nextVal = this.hasNextVal ? this.iterator.next() : null;
};

PeekingIterator.prototype.peek = function() {
    return this.nextVal;
};

PeekingIterator.prototype.next = function() {
    const result = this.nextVal;
    this.hasNextVal = this.iterator.hasNext();
    this.nextVal = this.hasNextVal ? this.iterator.next() : null;
    return result;
};

PeekingIterator.prototype.hasNext = function() {
    return this.hasNextVal;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
初始化O(1)O(1)
peek()O(1)O(1)
next()O(1)O(1)
hasNext()O(1)O(1)

总体空间复杂度：O(1)，只需要常数级别的额外空间来缓存下一个元素。

相关题目