Share a C++ solution using stack and vector iterator


  • 1
    P

    Similar idea with Zigzag Iterator. Except that this time we use stack to store the iterators.

    class Vector2D {
    public:
        Vector2D(vector<vector<int>>& vec2d) {
            for (int i = vec2d.size() - 1; i >=0 ; i--) {
                if (vec2d[i].begin() != vec2d[i].end())
                    iteratorStack.push(make_pair(vec2d[i].begin(), vec2d[i].end()));
            }
        }
    
        int next() {
            auto nextPair = iteratorStack.top();
            iteratorStack.pop();
            auto iterator = nextPair.first;
            iterator++;
            if (iterator != nextPair.second)
                iteratorStack.push(make_pair(iterator, nextPair.second));
            return *(nextPair.first);
        }
    
        bool hasNext() {
            return iteratorStack.size() != 0;
        }
    private:
        stack<pair<vector<int>::iterator, vector<int>::iterator>> iteratorStack;
    };

  • 0
    S

    you don't need to first pop the top and then push back again every time. Using reference like this:

    auto& nextPair = iteratorStack.top();
    int val = *(nexPair.first);
    if(++nextPair.first == nexePair.second){
        iteratorStack.pop();
    }
    return val;
    }
    

    Since the access order is FIFO, I prefer to use queue.


Log in to reply
 

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