RLE 迭代器

难度: Medium

我们可以使用游程编码(即 RLE )来编码一个整数序列。在偶数长度 encoding ( 从 0 开始 )的游程编码数组中，对于所有偶数 i ，encoding[i] 告诉我们非负整数 encoding[i + 1] 在序列中重复的次数。

例如，序列 arr = [8,8,8,5,5] 可以被编码为 encoding =[3,8,2,5] 。encoding =[3,8,0,9,2,5] 和 encoding =[2,8,1,8,2,5] 也是 arr 有效的 RLE 。

给定一个游程长度的编码数组，设计一个迭代器来遍历它。

实现 RLEIterator 类:

RLEIterator(int[] encoded) 用编码后的数组初始化对象。
int next(int n) 以这种方式耗尽后 n 个元素并返回最后一个耗尽的元素。如果没有剩余的元素要耗尽，则返回 -1 。

示例 1：

输入：
["RLEIterator","next","next","next","next"]
[[[3,8,0,9,2,5]],[2],[1],[1],[2]]
输出：
[null,8,8,5,-1]
解释：
RLEIterator rLEIterator = new RLEIterator([3, 8, 0, 9, 2, 5]); // 这映射到序列 [8,8,8,5,5]。
rLEIterator.next(2); // 耗去序列的 2 个项，返回 8。现在剩下的序列是 [8, 5, 5]。
rLEIterator.next(1); // 耗去序列的 1 个项，返回 8。现在剩下的序列是 [5, 5]。
rLEIterator.next(1); // 耗去序列的 1 个项，返回 5。现在剩下的序列是 [5]。
rLEIterator.next(2); // 耗去序列的 2 个项，返回 -1。 这是由于第一个被耗去的项是 5，
但第二个项并不存在。由于最后一个要耗去的项不存在，我们返回 -1。

提示：

2 <= encoding.length <= 1000
encoding.length 为偶
0 <= encoding[i] <= 10⁹
1 <= n <= 10⁹
每个测试用例调用next 不高于 1000 次

Submission

运行时间: 27 ms

内存: 16.7 MB

from typing import List

class RLEIterator:

    def __init__(self, encoding: List[int]):
        self.encoding = encoding
        self.index = 0
        self.count = 0

    def next(self, n: int) -> int:
        while self.index < len(self.encoding):
            if self.count + n > self.encoding[self.index]:
                n -= self.encoding[self.index] - self.count
                self.count = 0
                self.index += 2
            else:
                self.count += n
                return self.encoding[self.index + 1]
        return -1

# 示例用法
encoding = [3, 8, 0, 9, 2, 5]
obj = RLEIterator(encoding)
print(obj.next(2))  # 输出: 8
print(obj.next(1))  # 输出: 8
print(obj.next(1))  # 输出: 5
print(obj.next(2))  # 输出: -1

Explain

该题解利用两个指针（index和count）来模拟RLE迭代器的行为。index指向当前考虑的编码元素，而count记录当前元素已经返回的次数。在next函数中，首先检查是否有足够的元素可以返回。如果当前元素剩余的数量（encoding[index] - count）小于n，说明当前元素不足以满足请求，因此将n减去可用的数量，并将index向前移动到下一个元素。如果当前元素足够，则增加count并返回当前元素的值。如果所有元素都已被遍历完而仍未能满足n的要求，则返回-1。

时间复杂度: O(k) 其中k是next调用的次数

空间复杂度: O(n) 其中n是编码数组的长度

from typing import List

class RLEIterator:

    def __init__(self, encoding: List[int]):
        self.encoding = encoding  # 编码后的数组
        self.index = 0  # 当前考虑的元素的索引
        self.count = 0  # 当前元素已经返回的次数

    def next(self, n: int) -> int:
        while self.index < len(self.encoding):
            if self.count + n > self.encoding[self.index]:
                n -= self.encoding[self.index] - self.count  # 更新n为剩余需要的元素数量
                self.count = 0  # 重置count
                self.index += 2  # 移动到下一个元素
            else:
                self.count += n  # 更新已返回的次数
                return self.encoding[self.index + 1]  # 返回当前元素
        return -1  # 如果所有元素都遍历完还未找到足够的元素，返回-1

# 示例用法
encoding = [3, 8, 0, 9, 2, 5]
obj = RLEIterator(encoding)
print(obj.next(2))  # 输出: 8
print(obj.next(1))  # 输出: 8
print(obj.next(1))  # 输出: 5
print(obj.next(2))  # 输出: -1

Explore

在本题解中，假设输入数组`encoding`的长度总是偶数，因为每两个元素表示一对（数量和值）。如果`encoding`的长度为奇数，则其格式不符合预期，可能导致错误或未定义的行为。在实际实现中，如果遇到长度为奇数的数组，应该在初始化时检查并抛出异常，提示输入格式错误。

在提供的题解中，并没有直接处理`n`为零或负数的情况。如果`n`为零，按照逻辑，不需要返回任何元素，应直接返回当前的元素值或未来的某个元素值，但具体行为应由具体需求定义。对于`n`为负数的情况，在逻辑上不合理，因为从迭代器请求负数量的元素无意义。在实际应用中，应在方法开始时检查`n`的值，如果为零或负，应立即返回错误或特定的值，如-1或抛出异常，以避免逻辑错误。

返回-1是一种常见的方法，用于指示无法满足请求的情况，例如在尝试从已耗尽的数据源获取更多数据时。这种方式在许多编程实践中被接受，因为它允许调用者通过检查返回值来简单地处理这种情况，而不是处理异常，这可能会导致代码复杂度增加。然而，是否返回-1或抛出异常，应根据具体的应用场景和错误处理策略来确定。

当`self.count + n > self.encoding[self.index]`条件满足时，意味着当前考虑的元素的剩余数量不足以满足请求的`n`个元素。此时，需要将索引`self.index`移动到下一对元素，即跳过当前元素的值到下一个元素的数量。将`self.count`重置为0是因为新的元素尚未被返回过，需要从这个元素的全新计数开始。这是一个逻辑上必需的重置步骤，以确保每次处理新的元素时，数量的计数是准确的。