题目描述
思路解析动画文字版
每次查询从头扫时间线会越来越慢。
每个 key 的时间戳天然递增，存成数组后对 timestamp 做右边界二分。
① 每个 key 存一条按时间递增的 (timestamp, value) 列表：set 末尾追加 ⇒ 每个 key 的列表按时间有序，为 get 二分铺路。
② get(foo, 3)：找 timestamp ≤ 3 的「最后一条」：查询语义：最大的 timestamp ≤ t。
③ 二分 mid=0：ts=1 ≤ 3 ✓ → 记下 bar，往右找更大：可行就记下、并尝试往右找更晚的可行解。
④ 二分 mid=1：ts=4 ＞ 3 ✗ → 往左收：超过 t 的一律舍弃。
⑤ 区间收完 → 答案 ＝ timestamp=1 的 bar：最后一次记下的可行值就是答案。
一句话记住：每个 key 的时间戳天然递增，存成数组后对 timestamp 做右边界二分。
边界三连：本题真边界：太早、太晚、正好命中。
⑥ 雷区：为什么二分而不是每次从头扫？：有序列表上二分：单次 get 从 O(n) 降到 O(log n)。
面试追问 · 核心思路：思路：每 key 存有序 (ts,val) 列表；set 追加 O(1)，get 二分 floor。
面试追问 · timestamp 不递增怎么办：若乱序插入，需保持有序(插入 O(n))或改用有序结构。
面试追问 · 复杂度：复杂度：set O(1)，get O(log n)，空间 O(n)。
这题学完不要乱跳，下一步去对应专题 /leetcode-animation/ds?k=binarysearch 连刷同类题；卡住时用 AI 答疑问“get 为什么能二分”。
参考代码
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 ans复杂度
- 时间复杂度：set O(1) / get O(log n)，set 末尾追加 O(1)；get 在有序列表二分 O(log n)
- 空间复杂度：O(n)，存下所有 (timestamp,value) 共 n 条
可套用的代码模板
记牢：set 追加；get 二分找 ≤ t 最大 ts，可行就记答案右移、否则左收。
Python
# 时间键值存储 骨架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易错点
面试追问把动画讲成自己的话
追问整体思路是什么？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
寻找两个正序数组的中位数
LeetCode 4 · 困难 · 沿着 二分查找 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题