C#: Easy to Understand Solution with Explanation. (Accepted)


  • 0

    Basic Idea:

    • Initially we push all the NestedInteger in the nestedList into a stack from last to first
      • When we pop from the stack, it returns the very first element.
    • In HasNext()
      • Peek the top element of stack, and return true if it is an Integer.
      • If it is a list, further flatten it.
    • In Next()
      • Pop the top element in the stack
      • Since HasNext() has already flatten it, it is guaranteed to be an integer, simply return it.
    interface NestedInteger {
       //return true if this NestedInteger holds a single integer, rather than a nested list.
       bool IsInteger();
    
       //return the single integer that this NestedInteger holds, if it holds a single integer
       //return null if this NestedInteger holds a nested list
       int GetInteger();
    
       //return the nested list that this NestedInteger holds, if it holds a nested list
       //return null if this NestedInteger holds a single integer
       IList<NestedInteger> GetList();
    }
    
    public class NestedIterator {
        private Stack<NestedInteger> stack; 
        public NestedIterator(IList<NestedInteger> nestedList) {
            this.stack = new Stack<NestedInteger>();
            for (int i = nestedList.Count - 1; i >= 0; i--)
                this.stack.Push(nestedList[i]);
        }
    
        public bool HasNext() {
            while (stack.Count > 0) {
                NestedInteger top = stack.Peek();
                if (top.IsInteger())
                    return true;
                IList<NestedInteger> topList = stack.Pop().GetList();
                for (int i = topList.Count - 1; i >= 0; i--)
                    this.stack.Push(topList[i]);
            }
            return false;
        }
    
        public int Next() {
            return this.stack.Pop().GetInteger();
        }
    }
    

Log in to reply
 

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