LeetCode 341. 扁平化嵌套列表迭代器 Java实现思路栈 惰性展开使用栈保存待处理的 NestedInteger 元素保持顺序逆序入栈。hasNext() 负责将栈顶的嵌套列表逐步展开直到栈顶是整数或栈为空next() 弹出栈顶整数。这样可以做到惰性求值不需要一次性展平所有元素空间复杂度与嵌套深度相关。代码实现importjava.util.*;publicclassNestedIteratorimplementsIteratorInteger{// 栈中存放待处理的 NestedInteger栈顶为下一个待处理元素privateDequeNestedIntegerstack;publicNestedIterator(ListNestedIntegernestedList){stacknewArrayDeque();// 逆序入栈保证出栈顺序与列表顺序一致for(intinestedList.size()-1;i0;i--){stack.push(nestedList.get(i));}}OverridepublicIntegernext(){if(!hasNext()){thrownewNoSuchElementException();}// 此时栈顶一定是整数returnstack.pop().getInteger();}OverridepublicbooleanhasNext(){while(!stack.isEmpty()){NestedIntegertopstack.peek();if(top.isInteger()){returntrue;}else{// 栈顶是列表弹出并展开将其元素逆序压入栈stack.pop();ListNestedIntegerlisttop.getList();for(intilist.size()-1;i0;i--){stack.push(list.get(i));}}}returnfalse;}}注NestedInteger 接口由题目提供包含 isInteger()、getInteger()、getList() 方法。复杂度分析· 时间复杂度每个元素最多入栈、出栈一次总体 O(N)其中 N 为所有整数的数量。· 空间复杂度O(D)D 为最大嵌套深度栈的深度。最坏情况 O(N)。示例说明假设嵌套列表为 [[1,1],2,[1,1]]初始化逆序压入 [1,1]、2、[1,1]栈内容从栈顶到栈底[1,1], 2, [1,1]。hasNext()栈顶是列表弹出并展开压入两个 1栈变为1, 1, 2, [1,1]。next() 依次返回 1, 1, 2然后处理下一个列表最终返回 1, 1。其他实现简单展平如果允许一次性展平可以在构造函数中递归将所有整数存入 List然后用索引迭代。代码更简单但空间复杂度为 O(N)且失去了惰性求值的优势。publicclassNestedIteratorimplementsIteratorInteger{privateListIntegerlistnewArrayList();privateintindex0;publicNestedIterator(ListNestedIntegernestedList){flatten(nestedList);}privatevoidflatten(ListNestedIntegernestedList){for(NestedIntegerni:nestedList){if(ni.isInteger()){list.add(ni.getInteger());}else{flatten(ni.getList());}}}OverridepublicIntegernext(){returnlist.get(index);}OverridepublicbooleanhasNext(){returnindexlist.size();}}推荐使用栈实现更符合迭代器的设计意图。