0981. Time Based Key-Value Store¶
题目信息¶
- 题号:
0981
- 难度:
Medium
- 主题:
设计题、键值历史、时间查询
- 原题:
- 重点:
同一键可以在不同时间保存多个值;
get返回时间不晚于查询时刻的最新值,不存在时返回空字符串,所有set时间戳严格递增
题目重述¶
实现 TimeMap 类,用于保存字符串键在不同时间对应的值。set(key, value, timestamp) 在给定时间为 key 记录 value;同一个键可以多次写入并保留历史记录。
get(key, timestamp) 需要查找此前所有对该键的写入中,时间戳小于或等于查询时间的记录,并返回其中时间戳最大的那条记录的值。若该键没有符合条件的历史值,返回空字符串。所有 set 调用提供的时间戳保证严格递增。
键和值只包含小写英文字母和数字,长度均在 [1, 100] 范围内;1 <= timestamp <= 10^7,set 与 get 的总调用次数不超过 2 * 10^5。
自建示例¶
查询两个写入时间之间的历史值:
输入:
["TimeMap","set","set","get","get","get"]
[[],["color","red",5],["color","blue",10],["color",7],["color",10],["shape",12]]
输出:[null,null,null,"red","blue",""]
解释:时刻 7 能看到的最新 color 记录来自时刻 5;时刻 10 返回刚写入的 blue;shape 从未写入,因此返回空字符串。
查询时间早于该键的首次写入:
输入:
["TimeMap","set","get"]
[[],["mode","dark",8],["mode",3]]
输出:[null,null,""]
解释:mode 的唯一历史记录位于时刻 8,查询时刻 3 没有时间不晚于它的记录,因此返回空字符串。