900. RLE Iterator

We can use run-length encoding (i.e., RLE) to encode a sequence of integers. In a run-length encoded array of even length encoding (0-indexed), for all even i, encoding[i] tells us the number of times that the non-negative integer value encoding[i + 1] is repeated in the sequence.

• For example, the sequence arr = [8,8,8,5,5] can be encoded to be encoding = [3,8,2,5]. encoding = [3,8,0,9,2,5] and encoding = [2,8,1,8,2,5] are also valid RLE of arr.
  Given a run-length encoded array, design an iterator that iterates through it.

Implement the RLEIterator class:

• RLEIterator(int[] encoded) Initializes the object with the encoded array encoded.
• int next(int n) Exhausts the next n elements and returns the last element exhausted in this way. If there is no element left to exhaust, return -1 instead.

• Time : O(n)
• Space : O(n)

class RLEIterator {
    queue<pair<int, int>> order;
public:
    RLEIterator(vector<int>& encoding) {
        for(int i = 0; i < encoding.size(); i+=2) {
            if(encoding[i])
                order.push({encoding[i], encoding[i+1]});
        }
    }

    int next(int n) {
        int res = -1;
        while(n and !order.empty()) {
            int remove = min(n, order.front().first);
            n -= remove;
            if(!n) res = order.front().second;
            order.front().first -= remove;
            if(!order.front().first) order.pop();
        }
        return res;
    }
};

/**
 * Your RLEIterator object will be instantiated and called as such:
 * RLEIterator* obj = new RLEIterator(encoding);
 * int param_1 = obj->next(n);
 */