1656. 设计有序流
1656. 设计有序流
🟢 🔖 设计
数组
哈希表
数据流
🔗 力扣
LeetCode
题目
There is a stream of n
(idKey, value)
pairs arriving in an arbitrary order, where idKey
is an integer between 1
and n
and value
is a string. No two pairs have the same id
.
Design a stream that returns the values in increasing order of their IDs by returning a chunk (list) of values after each insertion. The concatenation of all the chunks should result in a list of the sorted values.
Implement the OrderedStream
class:
OrderedStream(int n)
Constructs the stream to taken
values.String[] insert(int idKey, String value)
Inserts the pair(idKey, value)
into the stream, then returns the largest possible chunk of currently inserted values that appear next in the order.
Example:
Input
["OrderedStream", "insert", "insert", "insert", "insert", "insert"]
[[5], [3, "ccccc"], [1, "aaaaa"], [2, "bbbbb"], [5, "eeeee"], [4, "ddddd"]]
Output
[null, [], ["aaaaa"], ["bbbbb", "ccccc"], [], ["ddddd", "eeeee"]]
Explanation
// Note that the values ordered by ID is ["aaaaa", "bbbbb", "ccccc", "ddddd", "eeeee"]. OrderedStream os = new OrderedStream(5); os.insert(3, "ccccc"); // Inserts (3, "ccccc"), returns []. os.insert(1, "aaaaa"); // Inserts (1, "aaaaa"), returns ["aaaaa"]. os.insert(2, "bbbbb"); // Inserts (2, "bbbbb"), returns ["bbbbb", "ccccc"]. os.insert(5, "eeeee"); // Inserts (5, "eeeee"), returns []. os.insert(4, "ddddd"); // Inserts (4, "ddddd"), returns ["ddddd", "eeeee"]. // Concatentating all the chunks returned: // [] + ["aaaaa"] + ["bbbbb", "ccccc"] + [] + ["ddddd", "eeeee"] = ["aaaaa", "bbbbb", "ccccc", "ddddd", "eeeee"] // The resulting order is the same as the order above.
Constraints:
1 <= n <= 1000
1 <= id <= n
value.length == 5
value
consists only of lowercase letters.- Each call to
insert
will have a uniqueid.
- Exactly
n
calls will be made toinsert
.
题目大意
有 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
。否则,返回一个空列表。
示例:
![](https://assets.leetcode-cn.com/aliyun-lc- upload/uploads/2020/11/15/q1.gif)
输入
["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
是一个数据流管理器,可以按照插入的顺序存储数据,并在 insert
方法被调用时,返回从当前指针位置连续的、按顺序的字符串。
初始化:
- 使用一个数组
order
存储数据流,长度为n
。 - 定义一个指针
ptr
,初始值为0
,表示当前可以输出的最左位置。
- 使用一个数组
插入逻辑:
- 将
value
存储在数组的索引位置idKey - 1
中(因为idKey
是 1-based,而数组是 0-based)。 - 检查从
ptr
开始是否有连续的非空值:- 如果有,逐个收集这些值并将
ptr
向后移动。
- 如果有,逐个收集这些值并将
- 返回收集到的值组成的数组。
- 将
复杂度分析
- 时间复杂度:
O(n)
,每次insert
操作最多遍历一次指针后的连续元素,因此最坏情况下遍历n
个元素。 - 空间复杂度:
O(n)
,使用了一个长度为n
的数组存储数据。
代码
/**
* @param {number} n
*/
var OrderedStream = function (n) {
this.order = new Array(n); // 存储数据的数组
this.ptr = 0; // 当前指针位置
};
/**
* @param {number} idKey
* @param {string} value
* @return {string[]}
*/
OrderedStream.prototype.insert = function (idKey, value) {
this.order[idKey - 1] = value; // 插入值
let answer = [];
// 从指针位置开始收集连续的非空值
while (this.order[this.ptr]) {
answer.push(this.order[this.ptr++]);
}
return answer;
};
/**
* Your OrderedStream object will be instantiated and called as such:
* var obj = new OrderedStream(n)
* var param_1 = obj.insert(idKey,value)
*/
相关题目
题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
---|---|---|---|---|---|
2424 | 最长上传前缀 | 并查集 设计 树状数组 4+ | 🟠 | 🀄️ 🔗 |