# 900. RLE Iterator

Write an iterator that iterates through a run-length encoded sequence.

The iterator is initialized by `RLEIterator(int[] A)`, where `A` is a run-length encoding of some sequence.  More specifically, for all even `i``A[i]` tells us the number of times that the non-negative integer value `A[i+1]` is repeated in the sequence.

The iterator supports one function: `next(int n)`, which exhausts the next `n` elements (`n >= 1`) and returns the last element exhausted in this way.  If there is no element left to exhaust, `next` returns `-1`instead.

For example, we start with `A = [3,8,0,9,2,5]`, which is a run-length encoding of the sequence `[8,8,8,5,5]`.  This is because the sequence can be read as “three eights, zero nines, two fives”.

Example 1:

``````Input: ["RLEIterator","next","next","next","next"], [[[3,8,0,9,2,5]],[2],[1],[1],[2]]
Output: [null,8,8,5,-1]
Explanation:
RLEIterator is initialized with RLEIterator([3,8,0,9,2,5]).
This maps to the sequence [8,8,8,5,5].
RLEIterator.next is then called 4 times:

.next(2) exhausts 2 terms of the sequence, returning 8.  The remaining sequence is now [8, 5, 5].

.next(1) exhausts 1 term of the sequence, returning 8.  The remaining sequence is now [5, 5].

.next(1) exhausts 1 term of the sequence, returning 5.  The remaining sequence is now [5].

.next(2) exhausts 2 terms, returning -1.  This is because the first term exhausted was 5,
but the second term did not exist.  Since the last term exhausted does not exist, we return -1.
``````

Note:

1. `0 <= A.length <= 1000`
2. `A.length` is an even integer.
3. `0 <= A[i] <= 10^9`
4. There are at most `1000` calls to `RLEIterator.next(int n)` per test case.
5. Each call to `RLEIterator.next(int n)` will have `1 <= n <= 10^9`.

``````class RLEIterator {
public:
RLEIterator(vector<int> A) {
for (int i = 0; i < A.size(); i += 2) {
if (A[i] != 0) seq.push_back({A[i + 1], A[i]});
}
}

int next(int n) {
for (auto &p : seq) {
if (p.second == 0) continue;
if (p.second >= n) {
p.second -= n;
return p.first;
}
n -= p.second;
p.second = 0;
}
return -1;
}

private:
vector<pair<int, int>> seq;
};
``````

``````class RLEIterator {
public:
RLEIterator(vector<int>& A): nums(A), cur(0) {}

int next(int n) {
while (cur < nums.size() && n > nums[cur]) {
n -= nums[cur];
cur += 2;
}
if (cur >= nums.size()) return -1;
nums[cur] -= n;
return nums[cur + 1];
}

private:
int cur;
vector<int> nums;
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/900

https://leetcode.com/problems/rle-iterator/

https://leetcode.com/problems/rle-iterator/discuss/168294/Java-Straightforward-Solution-O(n)-time-O(1)-space

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation