设计有序流

难度: Easy

有 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 。
- 否则，返回一个空列表。

示例：

输入
["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

Submission

运行时间: 89 ms

内存: 16.8 MB

class OrderedStream:

    def __init__(self, n: int):
        self.cache = dict()
        self.ptr = 1

    def insert(self, idKey: int, value: str) -> List[str]:
        self.cache[idKey] = value
        res = []
        if self.ptr == idKey:
            while idKey in self.cache:
                res.append(self.cache[idKey])
                idKey += 1
            self.ptr = idKey
        return res


# Your OrderedStream object will be instantiated and called as such:
# obj = OrderedStream(n)
# param_1 = obj.insert(idKey,value)

Explain

本题解采用字典存储输入的(id, value)对，并使用一个指针ptr来记录当前应该输出的连续id序列的起始点。插入操作首先将(id, value)对存储到字典中。如果当前插入的id等于ptr，则从该id开始，不断检查并输出连续的id值直到找不到为止，随后更新ptr指向下一个未输出的id。

时间复杂度: O(n)

空间复杂度: O(n)

class OrderedStream:

    def __init__(self, n: int):
        self.cache = dict()  # 存储id到value的映射
        self.ptr = 1  # 初始指针指向id 1

    def insert(self, idKey: int, value: str) -> List[str]:
        self.cache[idKey] = value  # 插入id和value到字典
        res = []  # 初始化返回结果列表
        if self.ptr == idKey:  # 如果当前id等于ptr，需要输出连续的id对应的值
            while idKey in self.cache:  # 当连续id存在于字典中时
                res.append(self.cache[idKey])  # 添加当前id对应的value到结果列表
                idKey += 1  # 移动到下一个id
            self.ptr = idKey  # 更新ptr到下一个未输出的id
        return res  # 返回结果列表

# Your OrderedStream object will be instantiated and called as such:
# obj = OrderedStream(n)
# param_1 = obj.insert(idKey,value)

Explore

使用字典存储id和value的对应关系可以方便地处理非连续的id输入，并且可以灵活地插入任意id而不需要考虑数组的大小或者初始化开销。在数组中，如果id范围很大但插入的id很少，会造成大量空间浪费。字典提供了更高的空间效率和灵活性，尤其是在id值不连续或者范围未知的情况下。

这种设计的优点是能够保证只有当我们能够输出一个连续的序列时才返回非空列表，从而确保输出的顺序性和完整性。缺点是，如果数据的输入顺序非常随机，可能会导致多次插入操作都不产生输出，直到某一个特定的id被插入后才输出一大批累积的数据，这在某些情况下可能会导致输出的延迟或者批处理输出，影响性能和即时性。

当id分布非常分散时，这种方法确实可能影响性能。因为每次插入操作都可能需要进行多次查找以确认连续的id，如果这些id间隔较大，则每次插入可能只处理少数几个id，甚至一个都处理不了，导致多次无效查找。这会增加算法的时间复杂度，尤其是在极端情况下，如每次插入的id都非常分散。

如果所有的id都被插入且顺序完全颠倒，例如先插入最大的id，再插入次大的id，一直到最小的id，OrderedStream类将在每次插入时都只返回空列表，直到最后一个id（即id 1）被插入。在这个时候，将会输出全部存储的值。这种情况下，OrderedStream类能够有效地返回正确的结果列表，但所有输出将会延迟到最后一个（即第一个按顺序）id被插入时。