29 ms C++ solution by simulating a recursive function


  • 0
    E
    class NestedIterator
    {
        stack<pair<vector<NestedInteger>::const_iterator, vector<NestedInteger>::const_iterator>> s;
    
        void nextHelper()
        {
            for (;;)
            {
                const auto frame = s.top();
    
                if (frame.first == frame.second)
                {
                    s.pop();
    
                    if (s.empty())
                    {
                        break;
                    }
                    else
                    {
                        ++s.top().first;
                    }
                }
                else if (frame.first->isInteger())
                {
                    break;
                }
                else
                {
                    s.emplace(frame.first->getList().cbegin(), frame.first->getList().cend());
                }
            }
        }
    
    public:
        NestedIterator(const vector<NestedInteger> &nestedList)
        {
            s.emplace(nestedList.cbegin(), nestedList.cend());
            nextHelper();
        }
    
        int next()
        {
            const auto result = s.top().first->getInteger();
    
            ++s.top().first;
            nextHelper();
    
            return result;
        }
    
        bool hasNext()
        {
            return !s.empty();
        }
    };
    
    

    Explanation: this solution is done by simulating this recursive function:

    void iterate(vector<NestedInteger>::const_iterator first, vector<NestedInteger>::const_iterator last)
    {
        while (first != last)
        {
            if (it->isInteger())
            {
                // <-- Stop at here after `next` is called.
            }
            else
            {
                iterate(it->getList().cbegin(), it->getList().cend());
            }
        }
    }
    

Log in to reply
 

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