LeetCode 981. 基于时间的键值存储
题目描述
题意分析
同一个
key可以在不同时间保存不同的值。查询timestamp时，要返回该键所有“不晚于查询时间”的记录中时间最大的那一条；不存在符合条件的记录就返回空串。新值不能覆盖旧值，因为之后仍可能查询较早时刻。题目保证所有
set调用的时间戳严格递增，因此同一个键的记录作为其中的子序列，也天然按时间递增，可以直接追加，不必重新排序。
解法：每个键保存有序历史，二分查前一条
核心思路
[!blue]
用哈希表
history按键分组，每个键对应一个历史列表，列表中的每个记录同时保存time和value。写入只需找到对应列表并追加；查询只在这一条列表中搜索，不受其他键的历史数量影响。直接找“最后一个时间不大于
timestamp”可以转成查找严格上界：令p为第一条时间大于查询时间的记录下标。如果存在符合条件的记录，它就一定是p - 1；若所有记录都符合条件，则把不存在的上界记为列表长度，仍然能统一取前一条。二分使用左闭右开区间
[left, right)。始终保持：left左边的记录时间都不大于查询时间，right及右边的记录时间都大于查询时间。初始两侧已确定的区域都是空的，left = 0、right = entries.size()。若中间记录时间小于等于目标，由于列表有序，它以及左边记录都符合条件，严格上界只能在后面，令
left = mid + 1。否则中间记录及右边都过晚，令right = mid，保留它作为可能的第一个过晚位置。每次都会缩短未确定区间，最终left == right，正是所求边界p。
p == 0表示连第一条记录都过晚，应返回空串；否则返回entries[p - 1].value。相等时间在二分中归到符合条件的一侧，所以恰好时刻的值不会漏掉，也不必另设命中分支。
解题步骤
- set 把时间和值一起追加到该键列表。
- get 在左闭右开区间中二分第一条时间 >timestamp 的记录。
- 边界为 0 返回空串，否则返回前一个记录的值。
Java 对不存在的键直接返回空串；Go 读取不存在的键得到空切片，长度为零，二分不执行，也会在同一边界判断中返回空串。查询时间晚于所有历史时，边界等于列表长度，返回最新记录。
get不修改历史，因此查询时间可以任意先后，只有写入时间需要遵守递增条件。
代码实现
class TimeMap {
private static class Entry {
int time;
String value;
Entry(int time, String value) {
this.time = time;
this.value = value;
}
}
private final Map<String, List<Entry>> history = new HashMap<>();
public void set(String key, String value, int timestamp) {
history.computeIfAbsent(key, k -> new ArrayList<>()).add(new Entry(timestamp, value));
}
public String get(String key, int timestamp) {
List<Entry> entries = history.get(key);
if (entries == null) {
return "";
}
int left = 0;
int right = entries.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (entries.get(mid).time <= timestamp) {
left = mid + 1;
} else {
right = mid;
}
}
return left == 0 ? "" : entries.get(left - 1).value;
}
}
type timeEntry struct {
time int
value string
}
type TimeMap struct {
history map[string][]timeEntry
}
func Constructor() TimeMap {
return TimeMap{
history: map[string][]timeEntry{},
}
}
func (t *TimeMap) Set(key, value string, timestamp int) {
t.history[key] = append(t.history[key], timeEntry{timestamp, value})
}
func (t *TimeMap) Get(key string, timestamp int) string {
entries := t.history[key]
left, right := 0, len(entries)
for left < right {
mid := left + (right-left)/2
if entries[mid].time <= timestamp {
left = mid + 1
} else {
right = mid
}
}
if left == 0 {
return ""
}
return entries[left-1].value
}
复杂度分析
- 时间复杂度：不计字符串本身的处理成本，哈希表操作按期望常数时间计，
set均摊 $O(1)$，get为 $O(\log(q+2))$，q是该键的历史条数，空历史也只有常数开销。- 空间复杂度：总空间为全部记录数加保留字符串的大小。
关键点总结
[!green]
查询的目标是“最后一条不大于时间戳”，可统一转成“第一条大于时间戳，再减一”。
易错点总结
[!yellow]
- 恰好等于查询时间的记录应保留，二分分支使用 <=。
- 不存在的键与早于第一条记录的查询都返回空串。
- 直接追加依赖时间戳递增；不能宣称这份实现支持任意乱序写入。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 1146. 快照数组 | 中等 | 同样保存有序历史并查找不晚于目标版本的最后记录，区别是快照版本由系统统一产生。 |
| 34. 在排序数组中查找元素的第一个和最后一个位置 | 中等 | 复用寻找严格上界的二分方式，再退一位得到符合时间条件的最后记录。 |