原文链接: https://leetcode-cn.com/problems/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.

 

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 rLEIterator = new RLEIterator([3, 8, 0, 9, 2, 5]); // This maps to the sequence [8,8,8,5,5].
rLEIterator.next(2); // exhausts 2 terms of the sequence, returning 8. The remaining sequence is now [8, 5, 5].
rLEIterator.next(1); // exhausts 1 term of the sequence, returning 8. The remaining sequence is now [5, 5].
rLEIterator.next(1); // exhausts 1 term of the sequence, returning 5. The remaining sequence is now [5].
rLEIterator.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.

 

Constraints:

• 2 <= encoding.length <= 1000
• encoding.length is even.
• 0 <= encoding[i] <= 109
• 1 <= n <= 109
• At most 1000 calls will be made to next.

中文题目

编写一个遍历游程编码序列的迭代器。

迭代器由 RLEIterator(int[] A) 初始化，其中 A 是某个序列的游程编码。更具体地，对于所有偶数 i，A[i] 告诉我们在序列中重复非负整数值 A[i + 1] 的次数。

迭代器支持一个函数：next(int n)，它耗尽接下来的  n 个元素（n >= 1）并返回以这种方式耗去的最后一个元素。如果没有剩余的元素可供耗尽，则  next 返回 -1 。

例如，我们以 A = [3,8,0,9,2,5] 开始，这是序列 [8,8,8,5,5] 的游程编码。这是因为该序列可以读作 “三个八，零个九，两个五”。

 

示例：

输入：["RLEIterator","next","next","next","next"], [[[3,8,0,9,2,5]],[2],[1],[1],[2]]
输出：[null,8,8,5,-1]
解释：
RLEIterator 由 RLEIterator([3,8,0,9,2,5]) 初始化。
这映射到序列 [8,8,8,5,5]。
然后调用 RLEIterator.next 4次。

.next(2) 耗去序列的 2 个项，返回 8。现在剩下的序列是 [8, 5, 5]。

.next(1) 耗去序列的 1 个项，返回 8。现在剩下的序列是 [5, 5]。

.next(1) 耗去序列的 1 个项，返回 5。现在剩下的序列是 [5]。

.next(2) 耗去序列的 2 个项，返回 -1。 这是由于第一个被耗去的项是 5，
但第二个项并不存在。由于最后一个要耗去的项不存在，我们返回 -1。

 

提示：

1. 0 <= A.length <= 1000
2. A.length 是偶数。
3. 0 <= A[i] <= 10^9
4. 每个测试用例最多调用 1000 次 RLEIterator.next(int n)。
5. 每次调用 RLEIterator.next(int n) 都有 1 <= n <= 10^9 。

通过代码

官方题解

方法一：维护下一个元素的位置和删除次数

分析

在调用 next() 函数时，我们不会真正删除剩余的元素（或者说改变数组 A 的值），而是维护两个变量 i 和 q，其中 i 表示迭代器当前指向的是元素 A[i + 1]，q 表示它已经被删除的次数，q 的值不会大于 A[i]。

例如，当数组 A 为 [1,2,3,4] 时，它表示的序列为 [2,4,4,4]。当 i 和 q 的值分别为 0 和 0 时，表示没有任何元素被删除；当 i 和 q 的值分别为 0 和 1 时，表示元素 A[0 + 1] = 2 被删除了 1 次；当 i 和 q 的值分别为 2 和 1 时，表示元素 A[2 + 1] = 4 被删除了 1 次，且之前的元素被全部删除。

算法

如果我们调用 next(n)，即删除 n 个元素，那么对于当前的元素 A[i + 1]，我们还可以删除的次数为 D = A[i] - q。

如果 n > D，那么我们会删除所有的 A[i + 1]，并迭代到下一个元素，即 n -= D; i += 2; q = 0。

如果 n <= D，那么我们删除的最后一个元素就为 A[i + 1]，即 q += D; return A[i + 1]。

[sol1]
class RLEIterator {
    int[] A;
    int i, q;

    public RLEIterator(int[] A) {
        this.A = A;
        i = q = 0;
    }

    public int next(int n) {
        while (i < A.length) {
            if (q + n > A[i]) {
                n -= A[i] - q;
                q = 0;
                i += 2;
            } else {
                q += n;
                return A[i+1];
            }
        }

        return -1;
    }
}

[sol1]
class RLEIterator(object):

    def __init__(self, A):
        self.A = A
        self.i = 0
        self.q = 0

    def next(self, n):
        while self.i < len(self.A):
            if self.q + n > self.A[self.i]:
                n -= self.A[self.i] - self.q
                self.q = 0
                self.i += 2
            else:
                self.q += n
                return self.A[self.i+1]
        return -1

复杂度分析

• 时间复杂度：$O(N + Q)$，其中 $N$ 是数组 A 的长度，$Q$ 是调用函数 next() 的次数。

• 空间复杂度：$O(N)$。

统计信息

通过次数	提交次数	AC比率
3608	7243	49.8%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言