284. 窥视迭代器
题目描述
已有一个整数迭代器，只提供两个方法：next() 取出下一个元素并前进一步，hasNext() 判断后面是否还有元素。请基于它实现 PeekingIterator 类，额外支持 peek 操作。
构造函数 PeekingIterator(nums)：接收这个整数迭代器 nums。
next()：取出接下来的那个元素并返回，迭代位置随之前进。hasNext()：还剩元素时返回 true，否则返回 false。peek()：只查看接下来的那个元素并返回它，迭代位置保持不动。
各语言的迭代器类型和构造写法可能不同，但都至少提供 next() 和 hasNext()。输入由方法名数组和参数数组组成，构造时的参数是迭代器要遍历的数组；输出按顺序给出每次调用的返回值，构造调用记为 null。
输入：nums = ["PeekingIterator","next","peek","next","next","hasNext"] commands = [[[1,2,3]],[],[],[],[],[]] 输出：[null,1,2,2,3,false]
解释：用 [1,2,3] 构造后：next 得到 1；peek 看到 2 但不前进；接着 next 依次得到 2 和 3；此时没有剩余元素，hasNext 返回 false。
数据范围
1 <= nums.length <= 10001 <= nums[i] <= 1000- 调用
next和peek时一定还有下一个元素。 next、hasNext、peek合计最多调用1000次。
进阶：怎样修改设计，让它不只适用于整数，而能用于任意类型的元素？
解题思路
多读一个元素当缓存：构造时就从底层迭代器取出第一个元素放进 top。peek 直接返回 top；next 先记下 top 作为答案，再从底层读下一个元素补进 top（底层读完则置为 None）；hasNext 只要判断 top 是否为 None。
为什么正确
任何时刻 top 都等于“调用者下一次 next 应该得到的元素”；top 为 None 当且仅当已经没有元素。
复杂度分析
三个方法都是 O(1) 时间，额外空间 O(1)（只缓存一个元素）。
易错点
不能直接用底层的 hasNext 判断：缓存里还有一个元素时，底层可能已经读完了，所以 hasNext 必须看 top。另外不要用 0 或 -1 当“空”的标记，数据里可能出现这样的值，用 None（或单独的布尔量）更稳妥。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class PeekingIterator:
def __init__(self, iterator):
self.it = iterator
self.top = None
if self.it.hasNext():
self.top = self.it.next()
def peek(self):
return self.top
def next(self):
ans = self.top
self.top = None
if self.it.hasNext():
self.top = self.it.next()
return ans
def hasNext(self):
return self.top is not Noneclass PeekingIterator implements Iterator<Integer> {
private Iterator<Integer> it;
private Integer top;
public PeekingIterator(Iterator<Integer> iterator) {
it = iterator;
top = null;
if (it.hasNext()) {
top = it.next();
}
}
public Integer peek() {
return top;
}
@Override
public Integer next() {
Integer ans = top;
top = null;
if (it.hasNext()) {
top = it.next();
}
return ans;
}
@Override
public boolean hasNext() {
return top != null;
}
}class PeekingIterator : public Iterator {
bool has;
int top;
public:
PeekingIterator(const vector<int>& nums)
: Iterator(nums) {
has = false;
top = 0;
if (Iterator::hasNext()) {
has = true;
top = Iterator::next();
}
}
int peek() {
return top;
}
int next() {
int ans = top;
has = false;
if (Iterator::hasNext()) {
has = true;
top = Iterator::next();
}
return ans;
}
bool hasNext() const {
return has;
}
};type PeekingIterator struct {
it *Iterator
top int
has bool
}
func Constructor(iter *Iterator) *PeekingIterator {
p := &PeekingIterator{it: iter}
p.has = false
if p.it.hasNext() {
p.has = true
p.top = p.it.next()
}
return p
}
func (this *PeekingIterator) hasNext() bool {
return this.has
}
func (this *PeekingIterator) next() int {
ans := this.top
this.has = false
if this.it.hasNext() {
this.has = true
this.top = this.it.next()
}
return ans
}
func (this *PeekingIterator) peek() int {
return this.top
}var PeekingIterator = function(iterator) {
this.it = iterator;
this.top = null;
if (this.it.hasNext()) {
this.top = this.it.next();
}
};
PeekingIterator.prototype.peek = function() {
return this.top;
};
PeekingIterator.prototype.next = function() {
const ans = this.top;
this.top = null;
if (this.it.hasNext()) {
this.top = this.it.next();
}
return ans;
};
PeekingIterator.prototype.hasNext = function() {
return this.top !== null;
};class PeekingIterator {
it: Iterator;
top: number | null;
constructor(iterator: Iterator) {
this.it = iterator;
this.top = null;
if (this.it.hasNext()) {
this.top = this.it.next();
}
}
peek(): number {
return this.top as number;
}
next(): number {
const ans = this.top as number;
this.top = null;
if (this.it.hasNext()) {
this.top = this.it.next();
}
return ans;
}
hasNext(): boolean {
return this.top !== null;
}
}