企业官网建设流程全解析

LeetCode 900 RLE 迭代器题解：用游标指针优雅遍历游程编码序列

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode

导读

本文围绕 LeetCode 900「RLE 迭代器」（RLE Iterator）展开，这道中等难度的设计题要求实现一个能够按需"耗尽"游程编码（Run-Length Encoding）序列的迭代器。文章将带你掌握游程编码的核心概念、理解"伪更新"游标遍历的精髓，并给出可直接运行的正确实现，同时结合本仓库的 游程编码与哈夫曼编码专题 与 设计题专题 深化对压缩算法与设计题套路（trade-off）的理解。

题目背景：什么是游程编码

在进入题目之前，先理解 RLE（Run-Length Encoding，游程编码）的本质。游程编码是一种简单的无损压缩算法，其基本思想是将重复且连续出现多次的字符用「（连续出现次数，某个字符）」来描述。

仓库中的 游程编码与哈夫曼编码专题 给出了一个直观的例子：字符串AAAAABBBBCCC可以被描述为：

5A4B3C

其中5A表示有 5 个连续的A，4B表示 4 个连续的B，3C表示 3 个连续的C。当文件中存在大量连续重复的二进制内容时（例如大面积纯色色块的 BMP 图像），这种编码能获得很好的压缩效果。

本题正是在此基础上提出的：给定一个游程编码数组，实现一个迭代器来遍历它解码后的原始序列。注意我们并不真正把序列展开存储，而是直接在编码数组上进行"逻辑遍历"，这正是本题的核心考点。

题目描述与示例

题目要求

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

• 迭代器由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]

逐步推演：

1. RLEIterator由RLEIterator([3,8,0,9,2,5])初始化，映射到序列[8,8,8,5,5]。
2. .next(2)耗去序列的 2 个项，返回8。现在剩下的序列是[8, 5, 5]。
3. .next(1)耗去序列的 1 个项，返回8。现在剩下的序列是[5, 5]。
4. .next(1)耗去序列的 1 个项，返回5。现在剩下的序列是[5]。
5. .next(2)耗去序列的 2 个项，返回-1。这是由于第一个被耗去的项是5，但第二个项并不存在。由于最后一个要耗去的项不存在，我们返回-1。

注意.next(2)之所以返回-1，是因为题目要求返回被耗去的最后一个元素——最后一个元素并不存在，因此即使前面还有 1 个元素可耗，也必须返回-1。这是一个非常关键的细节，也是本题最容易踩的坑。

数据规模提示

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

从数据规模可以看出：编码数组长度最多 1000、调用次数最多 1000，但单次n可以高达10^9，绝不能真的把编码序列展开成原始数组（元素总数可能高达500 × 10^9），只能在编码数组上做逻辑运算。

前置知识

• 哈夫曼编码和游程编码：可阅读仓库中的 游程编码与哈夫曼编码专题 完整了解两种无损压缩算法的原理。该专题还指出，实际无损压缩格式（如 PNG、GIF、PDF、ZIP）往往是先做游程编码、再做哈夫曼编码的组合使用。
• 设计题的基本套路：本题在仓库的 设计题专题 中被列为中等难度的代表题目。该专题的核心观点是：设计题基本是"选好数据结构，算法实现就水到渠成"，关键是针对特定问题做出恰当的设计选择（trade-off）。

思路分析

这是一个游程编码的典型题目。算法分为两个部分：初始化（RLEIterator构造函数）与调用next(n)。

思路一：物理更新数组（简单但低效）

最朴素的想法是：初始化时记住整个A；每次调用next(n)时：

1. 判断n是否大于A[i]（i从 0 开始）：
   • 如果n > A[i]，说明当前这一段的元素不够耗，移除数组前两项（把该段完全耗尽），更新n = n - A[i]，重复步骤 1。
   • 如果n <= A[i]，说明当前段元素足够，更新A[i] = A[i] - n，返回A[i + 1]。

这种做法的问题是每次都要物理修改/移除数组前部元素，需要移动元素，时间成本高，且会破坏原始数据。

思路二：伪更新游标（推荐，本仓库采用的解法）

不更新数组本身，而是做"伪更新"：用一个变量current记录当前访问到的数组位置（段索引）。这样既避免了数组元素的移动，也保留了原始数组。很多时候我们需要保留原始数据，那就必须用这种方法，本仓库的题解采用的就是这种方式。

维护两个核心状态：

• this.A：原始游程编码数组（不修改，只读取）。
• this.current：当前正在处理的"段"的起始下标（指向A中某个偶数位，即该段的 count 位置）。

每次调用next(n)时：

1. while循环：只要current未越界，且当前段的剩余数量A[current]小于n，说明该段不够耗，于是把n减去A[current]（代表耗光该段），current += 2跳到下一段。
2. 循环结束后，若current >= A.length，说明所有段都已耗尽，返回-1。
3. 否则，A[current] -= n（把当前段剩余数量扣减），返回A[current + 1]（该段对应的元素值）。

注意：这里虽然修改了A[current]（count 字段），但只是就地更新计数，并不会移动元素或改变数组结构，因此代价极低，同时对于"逻辑上已耗尽的段"我们通过推进current指针来跳过，符合"伪更新"的思想。

完整代码实现（JavaScript）

/** * @param {number[]} A */ var RLEIterator = function(A) { this.A = A; this.current = 0; }; /** * @param {number} n * @return {number} */ RLEIterator.prototype.next = function(n) { const A = this.A; while(this.current < A.length && A[this.current] < n){ n = n - A[this.current]; this.current += 2; } if(this.current >= A.length){ return -1; } A[this.current] = A[this.current] - n; // 更新Count return A[this.current + 1]; // 返回element }; /** * Your RLEIterator object will be instantiated and called as such: * var obj = new RLEIterator(A) * var param_1 = obj.next(n) */

代码逐步解析

• 构造函数：this.A = A保存编码数组，this.current = 0指向第一个段（下标 0 是 count，下标 1 是对应元素）。
• while 循环：A[this.current] < n表示当前段即使全部耗尽也满足不了n个元素的需求，因此必须跳过该段——n减去该段数量，current前进 2（一个段占两个数组元素）。该循环可能跳过多个段，属于累进式跳跃。
• 越界判断：循环结束后若current已经越界，说明已无元素可耗，返回-1。这也正好处理了示例中.next(2)只剩 1 个元素时的情形：第一个被耗去的项是5，但第二个项并不存在，因此返回-1。
• 命中返回：若current未越界，说明n个元素在该段内即可满足。此时更新A[current] -= n（记录该段被消耗的进度），返回A[current + 1]作为被耗去的最后一个元素。

复杂度分析

以A.length表示编码数组长度、m表示调用next的次数：

• 时间复杂度：整体上current指针只增不减，全部调用累加起来最多遍历完整个数组，因此m次调用的均摊时间复杂度为O(m + A.length)；单次调用最坏为O(A.length)（一次性跳过多段）。
• 空间复杂度：O(1)，只使用了两个状态变量，不需要额外存储（这也是"伪更新"方案相比"展开序列"方案的最大优势——后者在n高达10^9时根本无法落地）。

边界情况与易错点

1. 返回 -1 的判定时机：题目要求返回"耗去的最后一个元素"，当被耗元素不存在时必须返回-1，即使n个元素中的前几个仍然存在。这一点必须在循环结束后的越界判断中统一处理，而不能在循环中途提前返回。
2. count 恰好等于 n 的情况：当A[current] == n时，循环条件A[this.current] < n不成立，直接走到更新分支：A[current]变为 0，返回A[current + 1]。此时该段逻辑上已空，但current并未前进——这没有问题，因为下一次调用next时，若还需要消耗，A[current] < n（0 < n）将成立，循环会立即跳过该段。这是代码逻辑能够自洽的关键。
3. 空数组初始化：若A = []，构造函数正常运行，首次调用next时 while 条件current < A.length立即不成立，返回-1。
4. 不要真的展开序列：编码数组中 count 之和可能极大（每个 count 最高10^9，最多 500 段），任何形式的展开存储都会导致内存或时间爆炸，务必在编码数组上做逻辑运算。

在仓库中的定位与扩展阅读

本题目在仓库中属于中等难度设计题，可见于：

• 中等难度题目合集：与911. 在线选举、460. LFU 缓存等设计题并列。
• 设计题专题：作者精选的 6 道设计题之一，用于演示"选择合适数据结构/状态表示"这一核心设计套路。
• 题解总览 与 introduction.md：均收录了该题（标注 👍 推荐）。

如果希望彻底理解游程编码的来龙去脉以及它和哈夫曼编码的组合使用方式，请务必阅读 游程编码与哈夫曼编码专题，其中还探讨了"如何提取子序列"等编码策略问题，以及游程编码在纯色图片、CDN 图片存储等场景中的实际意义。该专题与本题目互为印证：理解压缩编码的存储结构，是写出高效遍历器的前提。

总结

RLE 迭代器是一道"看着简单、写对不易"的设计题，核心收获有三点：

1. 数据结构决定解法：在编码数组上用一个单调递增的游标current模拟序列遍历，避免了展开原始序列的空间爆炸，也避免了物理删除数组元素的额外开销。
2. "伪更新"思想的普适性：当需要保留原始数据、又要模拟消费进度时，用一个外部游标记录位置，往往比真正修改数据结构更优雅、更高效。
3. 边界处理的严谨性：-1的返回时机、count 恰好耗尽、空数组等边界情况，是这类迭代器题目能否一次写对的关键。

掌握这道题之后，再遇到"在线选举"（911. 在线选举）、"LFU 缓存"（460. LFU 缓存）等设计题时，你会更容易抓住"先定数据结构、再谈算法"的解题主线。

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode