LeetCode 284. 窥视迭代器 (Peeking Iterator) Java 实现题目理解设计一个迭代器在普通迭代器的 next() 和 hasNext() 基础上增加一个 peek() 方法返回下一个元素但不移动指针。核心思路缓存下一个元素用一个变量 cache 保存“提前取出”的下一个元素并用 hasCache 标记该缓存是否有效。· peek()如果缓存无效就从底层迭代器取一个放入缓存然后返回缓存如果缓存有效直接返回。· next()如果缓存有效返回缓存并清空否则直接从底层迭代器取。· hasNext()缓存有效 或 底层迭代器还有元素都返回 true。Java 代码importjava.util.Iterator;classPeekingIteratorimplementsIteratorInteger{privatefinalIteratorIntegeriterator;privateIntegercache;// 缓存的下一元素privatebooleanhasCache;// cache 是否有效publicPeekingIterator(IteratorIntegeriterator){this.iteratoriterator;this.hasCachefalse;}// 返回下一元素但不前进publicIntegerpeek(){if(!hasCache){cacheiterator.next();hasCachetrue;}returncache;}// 返回下一元素并前进OverridepublicIntegernext(){if(hasCache){hasCachefalse;Integerresultcache;cachenull;returnresult;}returniterator.next();}OverridepublicbooleanhasNext(){returnhasCache||iterator.hasNext();}}复杂度分析· 时间复杂度peek()、next()、hasNext() 均为 O(1)。· 空间复杂度O(1)只额外使用了一个缓存变量和一个布尔标记。关键点缓存机制peek() 会把元素提前取出并保存避免重复调用底层 next()。状态标记使用 hasCache 而不是判断 cache ! null可以兼容底层迭代器返回 null 的情况。hasNext() 逻辑只要缓存有效或底层还有元素就返回 true。remove() 方法Java 8 的 Iterator 接口提供了默认实现会抛出 UnsupportedOperationException本题无需关心如果需要委托可自行覆写但要注意缓存状态。
