Medium

341. Flatten Nested List Iterator

stacktreedepth-first-searchdesignqueueiterator

解題說明

Flatten Nested List Iterator

題目描述：給定一個巢狀的整數列表，實作一個迭代器來展平它。每個元素要麼是一個整數，要麼是一個列表（其元素也可能是整數或列表）。實作 next() 和 hasNext() 方法。

解題思路：使用堆疊（Stack）來模擬深度優先遍歷。初始化時將所有頂層元素逆序壓入堆疊。在 hasNext() 中，反覆檢查堆疊頂端：若是列表則取出、展開並逆序壓回堆疊；直到頂端是整數或堆疊為空。next() 直接彈出堆疊頂端的整數。這種惰性展開的方式避免一次性展平整個結構，效率更高。

C++ 解法

複雜度分析

時間複雜度：O(n) 攤銷 — 其中 n 為所有整數的總數。每個元素最多被壓入和彈出堆疊各一次。

空間複雜度：O(d) — 其中 d 為最大巢狀深度，堆疊中最多存放 d 層展開的元素。

虛擬碼

1. Constructor: push all top-level elements onto stack in reverse order
2. hasNext():
   a. While stack is not empty:
      - If top is an integer, return true
      - Else pop the list, push its elements in reverse order
   b. Return false
3. next():
   a. Get integer value from stack top
   b. Pop stack
   c. Return value

其他解法

預先完全展平 O(n)：在建構函式中用遞迴或迭代方式將整個巢狀結構展平成一維陣列，然後用索引迭代。簡單但失去了惰性求值的優勢，初始化時間和空間都是 O(n)。

遞迴迭代器：用遞迴函式配合 yield（在 Python 中）或手動維護遞迴狀態。概念上更自然但在 C++ 中實作較困難。

延伸思考

如果巢狀結構非常深（例如上千層），堆疊方法會有什麼問題？
如何支援雙向迭代（增加 hasPrev() 和 prev() 方法）？
惰性展開和預先展平在不同使用模式下（如只取前 k 個元素 vs 遍歷全部）各有什麼優劣？

Flatten Nested List Iterator — CaffeCode