写在前面

看完题解，这道题其实应该不难，可能是因为看了题解所以不觉得难，哈哈哈；感觉主要是理解题意，特别要注意注释中的内部函数。

  • 其实就相当于给你个vector，里面存储的数据类型是NestedInteger类,它可以是一个整数或者列表，列表中的类型又是NestedInteger，让你将它展开。
  • 题目给了三个内置函数:
    • bool isInteger():返回该NestedInteger是否是一个整数
    • int getInteger(): 如果NestedInteger 是整数，则可以调用这个函数
    • vector<NestedInteger> &getList(): 如果不是整数，在可以调用这个函数，返回一个vector，里面存储的是NestedInteger列表的内容。
  • 初始化展开或者栈实现

初始化时即展开

其实就是遍历一个vector，对于每一个元素，根据isInteger函数判断其类型，并调用相应的函数来获取其内容，因为我们不知道列表嵌套了多少层，因此需要用DFS来自动展开。需要用一个容器来保存展开的内容，为了方便存取内容并向后迭代，选用deque容器。

  • 要注意每一个取出的数据的类型，这样才能调用对应的函数获取正确的结果。

    class NestedIterator {
public:
NestedIterator(vector<NestedInteger> &nestedList) {
    // 依次取出 NestedInteger 类型
    for(int i=0;i<nestedList.size();i++){
        NestedInteger item=nestedList[i];
        // 判断并根据类型展开
        if(item.isInteger()){
            V.push_back(item.getInteger());
        }
        else{
            dfs(item);
        }
    }
}
// DFS递归展开
void dfs(NestedInteger N){
    for(int i=0;i<N.getList().size();i++){
        if(N.getList()[i].isInteger())
            V.push_back(N.getList()[i]);
        else
            dfs(N.getList()[i]);
    }
}
// deque头部并pop
int next() {
    int N=V[0].getInteger();
    V.pop_front();
    return N;   
}
// 根据大小来确定结尾
bool hasNext() {
    if(V.size()==0)
        return false;
    else 
        return true;
}
private:
deque<NestedInteger> V;
};

利用栈存储，需要时展开

一般的迭代器求值应该是「惰性的」，也就是说，如果你要一个结果，我就算一个（或是一小部分）结果出来，而不是一次把所有结果都算出来。(来自labuladong)

  • 利用栈的先进后出特性

    • 有了前面的铺垫，其实比较简单了，先将vector的所有NestedInteger逆序入栈。
    • hasNext()函数需要判断栈顶元素的类型，是isInteger还是列表类型，如果是Integer则返回true，从而可以调用next函数。反之，则列表展开，依次入栈，这里有个细节为了将用的时候再展开贯彻到底，将一个列表展开反序入栈后，返回值是hasNext()，而不需要像前文中的完全dfs展开。

    • 如果展开反序入栈后，栈顶是Integer类型，则返回true，反之将会再次展开。就做到了用的时候再展开。

      class NestedIterator {
public:
NestedIterator(vector<NestedInteger> &nestedList) {
// 逆序入栈
for(int i=nestedList.size()-1;i>=0;i--)
    S.push(nestedList[i]);
}
    
// 注意栈内存储的都是 NestedInteger
int next() {
int N=S.top().getInteger();
S.pop();
return N;

}
    
bool hasNext() {
// 栈为空则返回false
if(S.empty())
    return false;
NestedInteger N=S.top();
if(N.isInteger())
    return true;
else{
    S.pop();
    for(int i=N.getList().size()-1;i>=0;i--){
        S.push(N.getList()[i]);
    }
    return hasNext();
}
}
private:
// 利用栈存放数据
stack<NestedInteger> S;
};

$\cdots$ end $\cdots$