LC 341. 扁平化嵌套列表迭代器

题目描述

这是 LeetCode 上的 341. 扁平化嵌套列表迭代器 ，难度为 中等。

给你一个嵌套的整型列表。

请你设计一个迭代器，使其能够遍历这个整型列表中的所有整数。

列表中的每一项或者为一个整数，或者是另一个列表，其中列表的元素也可能是整数或是其他列表。

示例 1:

输入: [[1,1],2,[1,1]]

输出: [1,1,2,1,1]

解释: 通过重复调用 next 直到 hasNext 返回 false，next 返回的元素的顺序应该是: [1,1,2,1,1]。

示例 2:

输入: [1,[4,[6]]]

输出: [1,4,6]

解释: 通过重复调用 next 直到 hasNext 返回 false，next 返回的元素的顺序应该是: [1,4,6]。

提示：

• $1 <= nestedList.length <= 500$
• 嵌套列表中的整数值在范围 $[-10^6, 10^6]$ 内

---

DFS + 队列

由于所有的元素都是在初始化时提供的，因此一个朴素的做法是在初始化的时候进行处理。

由于存在嵌套，比较简单的做法是通过 DFS 进行处理，将元素都放至队列。

Java 代码：

public class NestedIterator implements Iterator<Integer> {

    Deque<Integer> queue = new ArrayDeque<>();

    public NestedIterator(List<NestedInteger> nestedList) {
        dfs(nestedList);
    }
    
    @Override
    public Integer next() {
        return hasNext() ? queue.pollFirst() : -1;
    }

    @Override
    public boolean hasNext() {
        return !queue.isEmpty();
    }

    void dfs(List<NestedInteger> list) {
        for (NestedInteger item : list) {
            if (item.isInteger()) {
                queue.addLast(item.getInteger());
            } else {
                dfs(item.getList());
            }
        }
    }
}

C++ 代码：

class NestedIterator {
public:
    deque<int> queue;
    NestedIterator(vector<NestedInteger> &nestedList) {
        dfs(nestedList);
    }
    
    int next() {
        if (hasNext()) {
            int result = queue.front();
            queue.pop_front();
            return result;
        }
        return -1;
    }
    
    bool hasNext() {
        return !queue.empty();
    }

    void dfs(const vector<NestedInteger> &list) {
        for (const NestedInteger &item : list) {
            if (item.isInteger()) {
                queue.push_back(item.getInteger());
            } else {
                dfs(item.getList());
            }
        }
    }
};

• 时间复杂度：构建迭代器的复杂度为 $O(n)$，调用 next 与 hasNext 的复杂度为 $O(1)$
• 空间复杂度：$O(n)$

---

递归 + 栈

另外一个做法是，我们不对所有的元素进行预处理。

而是先将所有的 NestedInteger 逆序放到栈中，当需要展开的时候才进行展开。

Java 代码：

public class NestedIterator implements Iterator<Integer> {

    Deque<NestedInteger> stack = new ArrayDeque<>();

    public NestedIterator(List<NestedInteger> list) {
        for (int i = list.size() - 1; i >= 0; i--) {
            NestedInteger item = list.get(i);
            stack.addLast(item);
        }
    }

    @Override
    public Integer next() {
        return hasNext() ? stack.pollLast().getInteger() : -1;
    }

    @Override
    public boolean hasNext() {
        if (stack.isEmpty()) {
            return false;
        } else {
            NestedInteger item = stack.peekLast();
            if (item.isInteger()) {
                return true;
            } else {
                item = stack.pollLast();
                List<NestedInteger> list = item.getList();
                for (int i = list.size() - 1; i >= 0; i--) {
                    stack.addLast(list.get(i));
                }
                return hasNext();
            }
        }
    }
}

C++ 代码：

class NestedIterator {
public:
    stack<NestedInteger> stk;
    NestedIterator(vector<NestedInteger> &nestedList) {
        for (int i = nestedList.size() - 1; i >= 0; i--) {
            stk.push(nestedList[i]);
        }
    }
    
    int next() {
        if (hasNext()) {
            NestedInteger ni = stk.top();
            stk.pop();
            return ni.getInteger();
        }
        return -1;
    }
    
    bool hasNext() {
        if (stk.empty()) {
            return false;
        } else {
            NestedInteger item = stk.top();
            if (item.isInteger()) {
                return true;
            } else {
                stk.pop();
                const vector<NestedInteger> &list = item.getList();
                for (int i = list.size() - 1; i >= 0; i--) {
                    stk.push(list[i]);
                }
                return hasNext();
            }
        }
    }
};

• 时间复杂度：构建迭代器的复杂度为 $O(n)$，hasNext 的复杂度为均摊 $O(1)$，next 严格按照迭代器的访问顺序（ 先 hasNext 再 next()）的话为 $O(1)$，防御性编程生效的情况下为均摊 $O(1)$
• 空间复杂度：$O(n)$

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.341 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。