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

题目描述

给你一个嵌套的整数列表 nestedList 。

每个元素要么是一个整数，要么是一个列表；
该列表的元素也可能是整数或者是其他列表。

请你实现一个迭代器将其扁平化，使之能够遍历这个列表中的所有整数。

实现扁平迭代器类 NestedIterator ：

NestedIterator(List<NestedInteger> nestedList) 用嵌套列表 nestedList 初始化迭代器。
int next() 返回嵌套列表的下一个整数。
boolean hasNext() 如果仍然存在待迭代的整数，返回 true ；否则，返回 false 。

你的代码将会用下述伪代码检测：

initialize iterator with nestedList
res = []
while iterator.hasNext()
    append iterator.next() to the end of res
return res

如果 res 与预期的扁平化列表匹配，那么你的代码将会被判为正确。

示例 1：

1
2
3

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

示例 2：

1
2
3

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

提示：

\(1\) \(≤\) \(nestedList.length\) \(≤\) \(500\)
嵌套列表中的整数值在范围 \([-10^6, 10^6]\) 内

1. 递归

(深度优先搜索dfs) \(O(n)\)

嵌套的整型列表是一个树形结构，树上的叶子节点对应一个整数，非叶节点对应一个列表。

在这棵树上深度优先搜索的顺序就是迭代器遍历的顺序。

我们可以先遍历整个嵌套列表，将所有整数存入一个数组，然后遍历该数组从而实现 next 和 hasNext 方法。

复杂度分析

时间复杂度：初始化为 \(O(n)\)，next 和 hasNext 为 \(O(1)\)。其中 \(n\) 是嵌套的整型列表中的元素个数。

空间复杂度：\(O(n)\)。需要一个数组存储嵌套的整型列表中的所有元素。

代码

C++

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * class NestedInteger {
 *   public:
 *     // Return true if this NestedInteger holds a single integer, rather than a nested list.
 *     bool isInteger() const;
 *
 *     // Return the single integer that this NestedInteger holds, if it holds a single integer
 *     // The result is undefined if this NestedInteger holds a nested list
 *     int getInteger() const;
 *
 *     // Return the nested list that this NestedInteger holds, if it holds a nested list
 *     // The result is undefined if this NestedInteger holds a single integer
 *     const vector<NestedInteger> &getList() const;
 * };
 */

class NestedIterator {
public:
    vector<int> res;
    int k = 0;

    NestedIterator(vector<NestedInteger> &nestedList) {
        dfs(nestedList);
    }

    void dfs(vector<NestedInteger> &nestedList) {
        for (auto &t : nestedList)
            if (t.isInteger()) res.push_back(t.getInteger());
            else dfs(t.getList());
    }

    int next() {
        return res[k++];
    }

    bool hasNext() {
        return k < res.size();
    }
};

/**
 * Your NestedIterator object will be instantiated and called as such:
 * NestedIterator i(nestedList);
 * while (i.hasNext()) cout << i.next();
 */

2. 迭代

(栈) \(O(n)\)

我们可以用一个栈来代替方法一中的递归过程。

当调用 hasNext 时我们将栈顶元素变为下一个要访问的整数，初始化时将迭代器倒序压入栈中，这样可以保证栈顶的迭代器为输入数组的第一个迭代器。

复杂度分析

时间复杂度：初始化和 next 为 \(O(1)\)，hasNext 为均摊 \(O(1)\)。

空间复杂度：\(O(n)\)。最坏情况下嵌套的整型列表是一条链，我们需要一个 \(O(n)\) 大小的栈来存储链上的所有元素。但在[1,[1,[1,[1,...,]]]]的情况下，栈中的迭代器数量最多为2，大大减少所用空间。

代码

C++

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * class NestedInteger {
 *   public:
 *     // Return true if this NestedInteger holds a single integer, rather than a nested list.
 *     bool isInteger() const;
 *
 *     // Return the single integer that this NestedInteger holds, if it holds a single integer
 *     // The result is undefined if this NestedInteger holds a nested list
 *     int getInteger() const;
 *
 *     // Return the nested list that this NestedInteger holds, if it holds a nested list
 *     // The result is undefined if this NestedInteger holds a single integer
 *     const vector<NestedInteger> &getList() const;
 * };
 */

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() {
        int res = stk.top().getInteger();
        stk.pop();
        return res;
    }

    bool hasNext() {
        while (!stk.empty()) {
            auto t = stk.top();
            if (t.isInteger()) return true;

            stk.pop();

            for (int i = t.getList().size() - 1; i >= 0; i--)
                stk.push(t.getList()[i]);
        }
        return false;
    }
};

/**
 * Your NestedIterator object will be instantiated and called as such:
 * NestedIterator i(nestedList);
 * while (i.hasNext()) cout << i.next();
 */