My cpp answer in 32ms, with brief explaination.


  • 0
    A

    Note:

    The concept "layer" I mentioned in annotation is like this:

    [[1,2],3,[4,[5]]] <-up

    ..1,2......4,[5]..

    .................5... <-low

    Two stacks are used to store two parameters in layers, one is iterator, the other is the end of current segment.

    class NestedIterator {
    private:
        stack<vector<NestedInteger>::const_iterator> nests;//iterators in layers
        stack<vector<NestedInteger>::const_iterator> layer_ends;//ends of chosen segments in layers
    public:
        NestedIterator(vector<NestedInteger> &nestedList) {
            nests.push(nestedList.cbegin());//start at cbegin
            layer_ends.push(nestedList.cend());//mark the cend
        }
    
        bool hasNext() {
            if (!nests.empty()) {
              //traverse elements in the list
                while (nests.top()!=layer_ends.top()) {
                  //if it is an integer
                    if ((*(nests.top())).isInteger()) return true;
                    
                  //if it is a nested list, go to lower layer, get the list and
                    const vector<NestedInteger>* next_layer=&(*(nests.top())).getList();
                    nests.push((*next_layer).cbegin());
                    layer_ends.push((*next_layer).cend());
                  //check the list
                    if (hasNext()) return true;
                    nests.pop(); layer_ends.pop();
                    
                    ++nests.top();//next element
                }
            }
            return false;
        }
    
        int next() {
            int integer=(*(nests.top())).getInteger();
          //if this layer is finished, return to the upper one
            while ((++nests.top())==layer_ends.top()) {
                nests.pop();
                layer_ends.pop();
                if (nests.empty()) break;
            }
            return integer;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.