Tricky but minimal stacking. C++ 26ms


  • 0
    H

    This is a solution with minimal stacking.
    I make sure that the curr iterator is always pointing to a valid integer.
    hasNext is very simple.
    next will update the whole structure.

    class NestedIterator {
    	typedef vector<NestedInteger>::const_iterator NestedIntPtr;
    private:
    	struct stkEntry {
    		NestedIntPtr iter;
    		NestedIntPtr end;
    		stkEntry(NestedIntPtr iter, NestedIntPtr end):iter{iter}, end{end} {}
    	};
    	NestedIntPtr curr;
    	NestedIntPtr curr_end;
    	stack<stkEntry> stk;
    	vector<NestedInteger>& motherList;
    
    public:
        NestedIterator(vector<NestedInteger> &nestedList): stk{}, motherList{nestedList} 
        {
            curr = nestedList.begin();
            curr_end = nestedList.end();
            while (1) {
    	        while (curr == curr_end) {
    	        	if (!stk.empty()) {
    		        	curr = stk.top().iter;
    		        	curr_end = stk.top().end;
    		        	curr++;
    		        	stk.pop();		
    	        	} else {
    	        	    return;
    	        	}
    	        }
    	        while (curr != curr_end && !curr->isInteger()) {
    	            if (curr->getList().size()==0) {
    	            	curr++;
    	            	continue;
    	            }
    	        	stk.push(stkEntry(curr, curr_end));
    	        	curr_end = curr->getList().end();
    	        	curr = curr->getList().begin();
    	        }
    	        if (curr == curr_end) {
    	        	continue;
    	        } else {
    	        	break;
    	        }
            }
        }
    
        bool hasNext() {
            if (stk.empty() && curr == curr_end)
            	return false;
            return true;
        }
    
        int next() {
            assert(curr != curr_end);
            assert(curr->isInteger());
            int ret = curr->getInteger();
            curr++;
            while (1) {
    	        while (curr == curr_end) {
    	        	if (!stk.empty()) {
    		        	curr = stk.top().iter;
    		        	curr_end = stk.top().end;
    		        	curr++;
    		        	stk.pop();		
    	        	} else {
    	        	    return ret;
    	        	}
    	        }
    	        while (curr != curr_end && !curr->isInteger()) {
    	            if (curr->getList().size()==0) {
    	            	curr++;
    	            	continue;
    	            }
    	        	stk.push(stkEntry(curr, curr_end));
    	        	curr_end = curr->getList().end();
    	        	curr = curr->getList().begin();
    	        }
    	        if (curr == curr_end) {
    	        	continue;
    	        } else {
    	        	break;
    	        }
            }
            return ret;
        }
    };
    

Log in to reply
 

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