解題說明
RLE Iterator
題目描述： 實作一個 RLE（Run-Length Encoding）迭代器。初始化時給定一個 RLE 編碼陣列，格式為 [count1, val1, count2, val2, ...]。next(n) 方法消耗接下來的 n 個元素，返回最後一個被消耗的元素。如果元素不夠，返回 -1。
解題思路：
- 指標追蹤：維護一個指標 idx 指向當前正在消耗的 run，以及該 run 中剩餘的數量。
- next(n)：不斷從當前 run 中消耗元素。如果當前 run 的剩餘數量 >= n，直接扣減並返回當前值。否則，消耗完當前 run 的所有剩餘元素，移到下一個 run。
- 如果所有 run 都消耗完還不夠 n 個，返回 -1。
- 關鍵：不需要展開整個序列，直接在 RLE 表示上操作即可。
C++ 解法
複雜度分析
時間複雜度：next() 均攤 O(1)，最壞 O(k)，其中 k 為 run 的數量。所有 next() 呼叫的總時間為 O(k)
空間複雜度：O(1) — 不計輸入陣列的額外空間
虛擬碼
1. Store encoding array and initialize index = 0
2. next(n):
a. While index < encoding length:
- If encoding[index] >= n:
- Subtract n from encoding[index]
- Return encoding[index + 1] (the value)
- Else:
- Subtract encoding[index] from n (consume entire run)
- Advance index by 2 (move to next run)
b. Return -1 (exhausted all elements)其他解法
-
完全展開：在構造時將 RLE 解碼為完整序列，用一個指標追蹤位置。next(n) 只需移動指標。缺點是空間複雜度可能很大（如果 count 很大），且構造時間長。
-
二分搜尋 + 前綴和：預計算每個 run 結束時的累積計數。next(n) 更新全域消耗計數，用二分搜尋找到對應的 run 和值。適合需要隨機存取的變體問題。
延伸思考
- 如果需要支持 prev(n) 操作（向前回退 n 個元素），如何設計？
- 如果 RLE 編碼中的 count 可以非常大（如 10^18），你的實作是否仍然正確？
- 如何擴展支持 peek() 操作（查看下一個元素但不消耗）？