900. 游程长度编码迭代器

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) 用编码数组 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^9
1 <= n <= 10^9
最多会对 next 进行 1000 次调用。

解题思路

这道题要求设计一个迭代器来处理游程长度编码（RLE）序列。关键在于理解编码格式：偶数位置存储计数，奇数位置存储对应的值。

核心思路：

维护当前处理的编码对位置（索引）
维护当前编码对中剩余的元素个数
对于每次 next(n) 调用，逐步消耗元素直到满足需求

算法流程：

初始化时保存编码数组，设置当前索引为 0
在 next(n) 中：
- 循环处理直到消耗完 n 个元素或没有更多元素
- 如果当前编码对的剩余计数不足，则完全消耗并移动到下一对
- 如果当前编码对的剩余计数足够，则直接扣除并返回对应值
- 跳过计数为 0 的编码对

优化细节：

使用 index 追踪当前编码对位置
使用 currentCount 追踪当前编码对剩余数量
处理边界情况：计数为 0 的编码对需要跳过

时间复杂度：每次 next 操作最坏情况下需要遍历整个编码数组，为 O(encoding.length) 空间复杂度：O(1)，只使用常数额外空间

代码实现

class RLEIterator {
private:
    vector<int> encoding;
    int index;
    int currentCount;
    
public:
    RLEIterator(vector<int>& encoding) : encoding(encoding), index(0), currentCount(0) {
        // 跳过开头计数为0的编码对
        while (index < encoding.size() && encoding[index] == 0) {
            index += 2;
        }
        if (index < encoding.size()) {
            currentCount = encoding[index];
        }
    }
    
    int next(int n) {
        while (n > 0 && index < encoding.size()) {
            if (currentCount >= n) {
                currentCount -= n;
                return encoding[index + 1];
            }
            
            n -= currentCount;
            index += 2;
            
            // 跳过计数为0的编码对
            while (index < encoding.size() && encoding[index] == 0) {
                index += 2;
            }
            
            if (index < encoding.size()) {
                currentCount = encoding[index];
            }
        }
        
        return -1;
    }
};

class RLEIterator:
    def __init__(self, encoding: List[int]):
        self.encoding = encoding
        self.index = 0
        self.current_count = 0
        
        # 跳过开头计数为0的编码对
        while self.index < len(self.encoding) and self.encoding[self.index] == 0:
            self.index += 2
        
        if self.index < len(self.encoding):
            self.current_count = self.encoding[self.index]

    def next(self, n: int) -> int:
        while n > 0 and self.index < len(self.encoding):
            if self.current_count >= n:
                self.current_count -= n
                return self.encoding[self.index + 1]
            
            n -= self.current_count
            self.index += 2
            
            # 跳过计数为0的编码对
            while self.index < len(self.encoding) and self.encoding[self.index] == 0:
                self.index += 2
            
            if self.index < len(self.encoding):
                self.current_count = self.encoding[self.index]
        
        return -1

public class RLEIterator {
    private int[] encoding;
    private int index;
    private int currentCount;

    public RLEIterator(int[] encoding) {
        this.encoding = encoding;
        this.index = 0;
        this.currentCount = 0;
        
        // 跳过开头计数为0的编码对
        while (index < encoding.Length && encoding[index] == 0) {
            index += 2;
        }
        
        if (index < encoding.Length) {
            currentCount = encoding[index];
        }
    }
    
    public int Next(int n) {
        while (n > 0 && index < encoding.Length) {
            if (currentCount >= n) {
                currentCount -= n;
                return encoding[index + 1];
            }
            
            n -= currentCount;
            index += 2;
            
            // 跳过计数为0的编码对
            while (index < encoding.Length && encoding[index] == 0) {
                index += 2;
            }
            
            if (index < encoding.Length) {
                currentCount = encoding[index];
            }
        }
        
        return -1;
    }
}

var RLEIterator = function(encoding) {
    this.encoding = encoding;
    this.index = 0;
    this.currentCount = 0;
    
    // 跳过开头计数为0的编码对
    while (this.index < this.encoding.length && this.encoding[this.index]

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

操作	时间复杂度	空间复杂度
构造函数	O(k)	O(1)
next()	O(k)	O(1)

其中 k 是编码数组的长度。在最坏情况下，next() 操作需要遍历整个编码数组。

题目描述#

解题思路#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

解题思路

代码实现

复杂度分析