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 遍歷全部)各有什麼優劣?