[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
。否则,返回一个空列表。
示例输入
示例
输入
["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
解题思路
这道题要求设计一个流(OrderedStream),能够按 id
递增的顺序获取 (id, value) 对,并在每次插入新元素时返回从当前 ptr
开始的最长递增 id 连续序列。简单来说,我们要通过一个指针 ptr
来记录流中当前的位置,并插入新的值。当 id = ptr
时,我们返回从当前指针位置开始的所有连续 id 的值
具体实现的思路如下:
使用一个数组
stream
来存储流中的值,并在每次插入时更新指针ptr
当插入新值时,我们检查从当前
ptr
开始,是否有连续的 id 对应的值存在。如果有,则将这些值返回,并更新ptr
为最后一个 id + 1
代码实现
class OrderedStream {
final String[] stream;
int ptr;
public OrderedStream(int n) {
stream = new String[n + 1];
ptr = 1;
}
public List<String> insert(int idKey, String value) {
stream[idKey] = value;
int start = ptr;
List<String> res = new ArrayList<>();
while (ptr < stream.length && stream[ptr] != null) {
res.add(stream[ptr]);
ptr++;
}
return res;
}
}
复杂度分析
时间复杂度:每次插入操作的时间复杂度是 O(n)(最坏情况,当插入的 id 是 ptr 后面一段连续 id 的最小值时,需要遍历整个流)。但是由于每次操作都是从当前
ptr
位置开始插入,时间复杂度不会超出 O(n)空间复杂度:O(n),因为我们使用一个大小为
n+1
的数组来存储流中的所有元素
总结
这道题虽然比较简单,但它很好地展示了如何设计一个有序流,并利用指针 ptr
来高效地返回连续 id 的值。通过合理使用数组存储和维护指针,我们能够在常数时间内完成插入操作,并根据当前指针位置返回相应的结果。其实这道题也让我想到,指针的概念在很多实际应用中都非常有用,能有效地减少不必要的重复计算和查找,提升程序性能
希望这篇分享能为你带来启发!如果你有任何问题或建议,欢迎在评论区留言,与我共同交流探讨。