C++ 15ms Beats 99.7% with engineering consideration


  • 0
    O
    • Don't find your next integer in hasNext() because it may be called multiple times.
    • Use struct instead of pair, for more readability and it's easier for you to write correct code.
    class NestedIterator {
    public:
        NestedIterator(vector<NestedInteger> &nestedList) {
            st.push(IterPair(nestedList.cbegin(), nestedList.cend()));
            PrepareNext();
        }
    
        int next() {
            auto& iter = st.top().iter;
            int res = iter->getInteger();
            ++iter;
            PrepareNext();
            return res;
        }
    
        bool hasNext() {
            return !st.empty();
        }
    
    private:
        using ConstIter=vector<NestedInteger>::const_iterator;
        
        struct IterPair {
            ConstIter iter, end;
            IterPair(ConstIter i, ConstIter e) : iter{i}, end{e} {}
        };
        
        stack<IterPair> st;
        
        void PrepareNext() {
            while (!st.empty()) {
                if (st.top().iter == st.top().end) {
                    st.pop();
                    if (st.empty())
                        break;
                    st.top().iter++;
                } else {
                    if (st.top().iter->isInteger()) 
                        break;
                    auto& l = st.top().iter->getList();
                    st.push(IterPair(l.cbegin(), l.cend()));
                }
            }
        }
    };
    

Log in to reply
 

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