摘要：前言的第一道題目，雖然分值才分，但是卻是中等難度的題目迭代器編寫一個遍歷游程編碼序列的迭代器。迭代器由初始化，其中是某個序列的游程編碼。迭代器支持一個函數，它耗盡接下來的個元素并返回以這種方式耗去的最后一個元素。

Weekly Contest 101的第一道題目，雖然分值才4分，但是卻是中等難度的題目RLE 迭代器：

編寫一個遍歷游程編碼序列的迭代器。
迭代器由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。
PS:Leetcode這次的競賽時間是1小時45分鐘是因為競賽開始了10分鐘，但是題目還是看不到

其實一開始做這個題目的時候我也是一頭霧水，首先游程編碼是一個我沒接觸過的概念，其次是這個題目描述說得太繞了。關于游程編碼的概念，可以從網上找到介紹。

我先從示例入手簡單講解一下題目：

首先我們要知道關于初始化的數組其實是經過游程編碼處理后的數組，即壓縮后的數組。先展示游程編碼前后的數組：

編碼后
[3,8,0,9,2,5]

編碼前
[8,8,8,5,5] 

根據題目的介紹，對編碼后的數組進行處理后：[(3,8),(0,9),(2,5)]。每個括號內的其實就是(數字出現次數,對應的數字).也就是題目中所說的:

對于所有偶數 i，A[i] 告訴我們在序列中重復非負整數值 A[i + 1] 的次數。

然后我們可以嘗試進行解碼：

解碼(3,8)得到數組[8,8,8]

解碼(0,9),由于次數為0，所以結果為[]

解碼(2,5)得到[5,5]

然后按照順序拼接起來[8,8,8,5,5]

而題目其實是要求我們根據輸入的編碼后的數組遍歷解碼(編碼前)的數組

/**
 * RLE 迭代器
 * @author RJH
 * create at 2018/9/9
 */
public class RLEIterator {
    /**
     * 當前原數據的索引，可以看做是一個指向當前訪問位置的指針
     */
    private int index=0;
    /**
     * 當前遍歷的元素，對應index+1的原數據的元素。其實是對應游程編碼解壓后的元素
     */
    private int element=-1;
    /**
     * 初始化的原數據，其實是游程編碼壓縮后的數組
     */
    private int[] data;

    public RLEIterator(int[] A) {
        data=A;
    }

    public int next(int n) {
        while (n>0){
            if(index>data.length-2){
                element=-1;
                break;
            }
            //當前元素出現次數
            int times=data[index];
            if(times>0){
                if(times>n){
                    data[index]=times-n;
                    element=data[index+1];
                }else{
                    //代表對應的元素已經遍歷完了，所以設為0
                    data[index]=0;
                    //當前的元素則為index+1的元素
                    element=data[index+1];
                    index+=2;
                }
                n-=times;
            }else{
                //次數為0，直接訪問下一個偶數index對應的次數
                index+=2;
            }
        }
        return element;
    }
}