图解LeetCode——1656. 设计有序流（难度：简单）

一、题目

有 n 个 (id, value) 对，其中 id 是 1 到 n 之间的一个整数，value 是一个字符串。不存在 id 相同的两个 (id, value) 对。

设计一个流，以 任意 顺序获取 n 个 (id, value) 对，并在多次调用时 按 id 递增的顺序 返回一些值。

实现 OrderedStream 类：

OrderedStream(int n) 构造一个能接收 n 个值的流，并将当前指针 ptr 设为 1 。
String[] insert(int id, String value) 向流中存储新的 (id, value) 对。存储后：

• 如果流存储有 id = ptr 的 (id, value) 对，则找出从 id = ptr 开始的 最长 id 连续递增序列 ，并 按顺序 返回与这些 id 关联的值的列表。然后，将 ptr 更新为最后那个 id + 1 。
• 否则，返回一个空列表。

二、示例

2.1> 示例1：

【输入】
["OrderedStream", "insert", "insert", "insert", "insert", "insert"]
[[5], [3, "ccccc"], [1, "aaaaa"], [2, "bbbbb"], [5, "eeeee"], [4, "ddddd"]]
【输出】
[null, [], ["aaaaa"], ["bbbbb", "ccccc"], [], ["ddddd", "eeeee"]]
【解释】
OrderedStream os= new OrderedStream(5);
os.insert(3, "ccccc"); // 插入 (3, "ccccc")，返回 []
os.insert(1, "aaaaa"); // 插入 (1, "aaaaa")，返回 ["aaaaa"]
os.insert(2, "bbbbb"); // 插入 (2, "bbbbb")，返回 ["bbbbb", "ccccc"]
os.insert(5, "eeeee"); // 插入 (5, "eeeee")，返回 []
os.insert(4, "ddddd"); // 插入 (4, "ddddd")，返回 ["ddddd", "eeeee"]

提示：

• 1 <= n <= 1000
• 1 <= id <= n
• value.length == 5
• value 仅由小写字母组成
• 每次调用 insert 都会使用一个唯一的 id
• 恰好调用 n 次 insert

三、解题思路

其实这道题的难点不在于题目的解题思路上，而是在于题目的阅读上。我自己也是看了好几遍才明白了它具体是要实现什么样的执行逻辑。其实这里面起到主导作用的就是指针ptr，因为它会影响到整个方法的返回值。根据ptr所在的不同位置，有如下几种返回结果：

情况一：当新插入的元素没有插入到prt所指向的位置时，插入元素后，方法会返回空集合。
情况二：当新插入的元素插入到prt所指向的位置时，插入元素后，则将该元素作为结果返回。但此时还没有结束，prt执行加1操作指向下一个位置，如果这个位置上已经有元素了，那么继续作为结果返回且prt再次加1，直到prt指向的位置是空的，结束方法逻辑。

那么，在其构造方法中，通过入参n来确定可以容纳的元素个数，由于题目中已经确定n的取值是大于等于1并且小于等于1000，所以，我们可以通过创建一个数组的数据结构，来支持后续的操作。那么数组的下标index就对应着插入方法insert(int idKey, String value)的第一个入参idKey，那么，由于数组是从0开始的，所以我们初始化数组长度的时候，要初始化n + 1的长度，而实际操作过程中，我们其实只会用到index=1到index=n，index=0的位置永远都是空的。

好了，根据上面我们确定的这道题的解题思路后，我们以创建n等于5，分别插入[3, "ccccc"], [1, "aaaaa"], [2, "bbbbb"], [5, "eeeee"], [4, "ddddd"]为例，看一下具体的操作逻辑是怎么样的？

首先，我们创建一个长度为6的数组（即：n + 1），当插入[3, "ccccc"]时，由于index=3的位置上没有插入过其他元素，所以按照题意，直接返回空集合即可。由于prt现在指向1的位置，而插入位置是3，所以，prt不做任何变动。具体操作如下图所示：

然后，我们再插入[1, "aaaaa"]，由于此时prt等于1，元素插入到了prt指向的位置，所以，根据题意，我们返回["aaaaa"]，同时prt指向加1操作，即：指向了下标为2的位置。由于下标为2的位置上没有插入过元素，所以，方法逻辑执行完毕，**返回["aaaaa"]**。具体操作如下图所示：

接下来，我们继续插入[2, "bbbbb"]，由于此时prt等于2，元素插入到了prt指向的位置，所以，根据题意，我们返回["bbbbb"]，同时prt指向加1操作，但是我们发现，prt指向的下标为3的位置上，已经存在元素“ccccc”了，所以，我们也将它一起作为返回值返回出去，此时prt再次执行加1操作，那么下标为4的位置上，元素是空的，所以，结束方法逻辑，**返回["bbbbb", "ccccc"]**。具体操作如下图所示：

那么对于插入后续插入的[5, "eeeee"]和[4, "ddddd"]，操作跟上面的一样的，这里就不进行赘述了。直接看一下，下图的具体操作就可以了：

关于具体的代码实现，请参照：四、代码实现。

四、代码实现

class OrderedStream {
    int ptr;
    String[] elements;
    public OrderedStream(int n) {
        elements = new String[++n];
        ptr = 1;
    }
    
    public List<String> insert(int idKey, String value) {
        List<String> result = new ArrayList();
        elements[idKey] = value; 
        if (idKey == ptr) {           
            while(ptr < elements.length && elements[ptr] != null) {
                result.add(elements[ptr]);   
                ptr++;        
            }
        } 
        return result;
    }
}

今天的文章内容就这些了：

写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的 点赞 & 分享 。

更多技术干货，欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享，每天更新」