基于时间的键值存储 图解题解
同一个 key 的时间戳天然有序，查「不超过某时刻的最新值」就是在有序列表上做右边界二分。
像翻一个人的日记找「某天之前最近的那篇」：日记按日期顺序排好，不用从第一篇翻到最后，直接翻到中间看日期——比目标晚就往前翻，比目标早或相等就记下来再往后探更晚的可行记录。每个 key 的时间戳天然递增，set 追加维护有序，get 对时间戳做右边界二分，找不超过 t 的最大时间戳对应的值。
这道题到底在问什么
- 示例
- set(foo,bar,1), set(foo,baz,4), get(foo,3) → bar
最优解：一步一步想明白
- 3每次查询从头扫时间线会越来越慢。
- 4每个 key 的时间戳天然递增，存成数组后对 timestamp 做右边界二分。
- 5set 末尾追加 ⇒ 每个 key 的列表按时间有序，为 get 二分铺路。
- 6查询语义：最大的 timestamp ≤ t。
- 7可行就记下、并尝试往右找更晚的可行解。
- 8超过 t 的一律舍弃。
- 9最后一次记下的可行值就是答案。
- 12一句话记住：每个 key 的时间戳天然递增，存成数组后对 timestamp 做右边界二分。
- 15有序列表上二分：单次 get 从 O(n) 降到 O(log n)。
- 22这题学完不要乱跳，下一步去对应专题 /leetcode-animation/ds?k=binarysearch 连刷同类题；卡住时用 AI 答疑问“get 为什么能二分”。
⚠️ 容易写错的地方
✗ 错：get 时从头线性扫整条时间线
✓ 对：对 timestamp 列表二分
set 保证 timestamp 递增有序，二分把单次 get 从 O(n) 降到 O(log n)。
✗ 错：二分去找「正好 == t」
✓ 对：找「≤ t 的最大 timestamp」(floor)
t 时刻常常没有恰好的记录，要的是不超过 t 的最近一条。
✗ 错：没有任何 ≤ t 的记录时报错
✓ 对：返回空字符串 ""
若所有 timestamp 都 ＞ t，按题意返回 ""。
完整代码（Python / C++ / Java）
Python
class TimeMap:
def __init__(self):
self.store = {}
def set(self, key, value, timestamp):
self.store.setdefault(key, []).append((timestamp, value))
def get(self, key, timestamp):
arr = self.store.get(key, [])
l, r = 0, len(arr) - 1
ans = ""
while l <= r:
m = (l + r) // 2
if arr[m][0] <= timestamp:
ans = arr[m][1]
l = m + 1
else:
r = m - 1
return ansC++
class TimeMap {
unordered_map<string, vector<pair<int,string>>> mp;
public:
void set(string key, string value, int timestamp) {
mp[key].push_back({timestamp, value});
}
string get(string key, int timestamp) {
auto& arr = mp[key];
int l = 0, r = (int)arr.size() - 1;
string ans = "";
while (l <= r) {
int m = (l + r) / 2;
if (arr[m].first <= timestamp) {
ans = arr[m].second;
l = m + 1;
} else {
r = m - 1;
}
}
return ans;
}
};Java
class TimeMap {
Map<String, List<int[]>> times = new HashMap<>();
Map<String, List<String>> values = new HashMap<>();
public void set(String key, String value, int timestamp) {
times.computeIfAbsent(key, k -> new ArrayList<>()).add(new int[]{timestamp});
values.computeIfAbsent(key, k -> new ArrayList<>()).add(value);
}
public String get(String key, int timestamp) {
List<int[]> ts = times.getOrDefault(key, new ArrayList<>());
List<String> vs = values.getOrDefault(key, new ArrayList<>());
int l = 0, r = ts.size() - 1;
String ans = "";
while (l <= r) {
int m = (l + r) / 2;
if (ts.get(m)[0] <= timestamp) {
ans = vs.get(m);
l = m + 1;
} else {
r = m - 1;
}
}
return ans;
}
}套路模板 · 有序时间线二分骨架
# 时间键值存储 骨架
store = defaultdict(list) # key -> [(ts, val), ...] 时间递增
def set(key, val, ts):
store[key].append((ts, val)) # 递增 ⇒ 直接追加 O(1)
def get(key, t):
arr = store[key]; lo, hi, ans = 0, len(arr)-1, ""
while lo <= hi: # 二分找 ≤ t 的最大 ts
mid = (lo + hi) // 2
if arr[mid][0] <= t: ans = arr[mid][1]; lo = mid + 1
else: hi = mid - 1
return ans复杂度
时间复杂度
set O(1) / get O(log n)
set 末尾追加 O(1)；get 在有序列表二分 O(log n)
空间复杂度
O(n)
存下所有 (timestamp,value) 共 n 条
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 基于时间的键值存储 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
整体思路是什么？+
用哈希表 key → 一条 (timestamp,value) 列表。set：因为 timestamp 递增，直接 append，O(1)。get(key,t)：在该 key 的有序列表上二分，找 ≤ t 的最大 timestamp 对应的 value，找不到返回 ""，O(log n)。
这道题为什么用「二分查找」，换最直接的暴力解会差在哪？+
二分查找抓住了本题的结构特征，把暴力解里重复的工作省掉；暴力解通常要多嵌套一层枚举，数据一大就超时。具体对比见上文「暴力解及其卡点」与「最优解逐步推演」两节。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。