题目描述
思路解析
一句话答案：LeetCode 981 基于时间的键值存储：同一个键的时间戳递增天然有序，get 时二分找不晚于 t 的最近一次值，找不到返回空串，单次查询 O(log n)、空间 O(总记录数)。
TimeMap 的 get 到底该返回哪次存的值
TimeMap 干两件事：set(key, value, timestamp) 把一次赋值连同发生的时刻存起来；get(key, timestamp) 返回这个键在不晚于该时刻的最近一次赋的值，没赋过就返回空串。题面里 set("foo","A6",6) 后，get("foo",7) 得 "A6"、get("foo",2) 得 "A1"，都是取该时刻往前最近的一次。同一个键的 timestamp 严格递增地存入。
同一个键查一次就从最新往回翻，慢在哪
get 每查一次，最直接的做法是把这个键的记录从最新往回翻，碰到第一个时间戳不晚于 t 的就停。一个键存了 n 条，查很早的时刻最坏要翻遍全部 n 条，单次查询是 O(n)。key 存得越多、查得越勤越拖不动，可记录本就按时间排好序，逐条翻等于把这份有序扔着不用。
同一个键的时间戳只增不减，正好落进二分的门槛
省下这趟线性翻找，靠题目送的一句保证：同一个键的 timestamp 严格递增。set 按时间先后一条条追加，每个键的记录列表天生按时间戳从小到大排好，不用再排。找「不晚于 t 的最近一次」就是在有序时间戳里找 ≤ t 里最大的那个，有序数组上定位边界值正是二分查找的活：每比一次中点就甩掉一半记录。也因为有序不用自己维护，set 只管往列表尾追加、O(1) 就完事。
中点时间戳和 t 比完，往哪半收、候选怎么留
二分用两个指针 l、r 圈住候选段，起初 l=0、r=n-1，这是两端都算数的闭区间 [l,r]。再备 ans 存最好答案、初值空串。每轮取中点 mid=(l+r)//2，拿 arr[mid] 时间戳和 t 比：≤ t 是合法候选，先记进 ans，可右边也许还有更晚、仍不晚于 t 的，那才算「最近」，于是 l 跳到 mid+1 往右探；> t 太晚，右边只会更晚一起丢，r 退到 mid-1。循环写 while l<=r，l==r 时还剩一格要查。
foo 存了 A1、A6，查 7 和查 2 各走几轮
题面的 foo 按时间戳存两条：0 号 (1,"A1")、1 号 (6,"A6")。查 get("foo",7)：l=0、r=1，mid=0 时间戳 1 ≤ 7，记 ans="A1"、l 到 1；再 mid=1，时间戳 6 ≤ 7，更新 ans="A6"、l 到 2，超过 r，返回 "A6"。查 get("foo",2)：mid=0 时间戳 1 ≤ 2，记 ans="A1"、l 到 1；再 mid=1，时间戳 6 > 2 太晚，r 退到 0，返回 "A1"。
查得比最早那次还早，返回空串别硬凑一个值
单个键 n 条记录，二分把查询压到约 log₂n 次比较，单次 get 是 O(log n)；set 尾部追加 O(1)；空间存下全部 (时间戳, 值) 对，O(总记录数)。坑都在收尾。ans 初值必须空串：查比最早记录还早的时刻，r 被逼到 -1、没记下候选，就返回空串，若返回最小时间戳那条便是硬塞题目没要的值。时间戳 ≤ t 那支别当场 return，右边可能还有仍不晚于 t 的更晚记录，提前收手会拿到偏早的值，记下再往右才对。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
核心就一句：在有序时间戳里二分找「≤ t 的最大值」。ts[mid]≤t 就记下候选并往右，否则往左。
开始二分：l 指向最左、r 指向最右，搜索范围是整串时间戳。还没有候选答案。
范围 [0, 6] 取中点 mid = 3，那一格的时间戳是 6。拿它和查询时刻 7 比较。
时间戳 6 ≤ 7，是个合法候选——先把它记进 ans（绿色这格）。但右边也许有更晚、仍不超过 7 的，所以 l 往右挪到 4 继续找。
范围 [4, 6] 取中点 mid = 5，那一格的时间戳是 12。拿它和查询时刻 7 比较。
时间戳 12 比 7 还晚（标红这格），不能要；它右边的更晚，一起丢掉。r 往左挪到 4。
范围 [4, 4] 取中点 mid = 4，那一格的时间戳是 9。拿它和查询时刻 7 比较。
时间戳 9 比 7 还晚（标红这格），不能要；它右边的更晚，一起丢掉。r 往左挪到 3。
范围缩成空，二分结束。最后记下的候选是 6 时刻的 A6（绿色这格），这就是答案。
边界要演一遍：查询时刻早于所有记录时，ans 全程没机会被记下，最后老实返回空串。
再查一次，这回 开始二分：l 指向最左、r 指向最右，搜索范围是整串时间戳。还没有候选答案。
范围 [0, 6] 取中点 mid = 3，那一格的时间戳是 6。拿它和查询时刻 0 比较。
时间戳 6 比 0 还晚（标红这格），不能要；它右边的更晚，一起丢掉。r 往左挪到 2。
范围 [0, 2] 取中点 mid = 1，那一格的时间戳是 3。拿它和查询时刻 0 比较。
时间戳 3 比 0 还晚（标红这格），不能要；它右边的更晚，一起丢掉。r 往左挪到 0。
范围 [0, 0] 取中点 mid = 0，那一格的时间戳是 1。拿它和查询时刻 0 比较。
时间戳 1 比 0 还晚（标红这格），不能要；它右边的更晚，一起丢掉。r 往左挪到 -1。
范围缩成空，全程没记下任何候选，说明这个时刻之前没存过值，返回空串。
再演一个最常见的：查询时刻夹在两个时间戳之间，二分回退到它之前最近一次存的值。
查 开始二分：l 指向最左、r 指向最右，搜索范围是整串时间戳。还没有候选答案。
范围 [0, 6] 取中点 mid = 3，那一格的时间戳是 6。拿它和查询时刻 5 比较。
时间戳 6 比 5 还晚（标红这格），不能要；它右边的更晚，一起丢掉。r 往左挪到 2。
范围 [0, 2] 取中点 mid = 1，那一格的时间戳是 3。拿它和查询时刻 5 比较。
时间戳 3 ≤ 5，是个合法候选——先把它记进 ans（绿色这格）。但右边也许有更晚、仍不超过 5 的，所以 l 往右挪到 2 继续找。
范围 [2, 2] 取中点 mid = 2，那一格的时间戳是 4。拿它和查询时刻 5 比较。
时间戳 4 ≤ 5，是个合法候选——先把它记进 ans（绿色这格）。但右边也许有更晚、仍不超过 5 的，所以 l 往右挪到 3 继续找。
范围缩成空，二分结束。最后记下的候选是 4 时刻的 A4（绿色这格），这就是答案。
三个高频追问：为何能二分、set 为何 O(1) 不用排序、键不存在时返回空串。
参考代码
class TimeMap: def __init__(self): self.store = {} # key -> [(ts, val), ...] def set(self, key, value, ts): self.store.setdefault(key, []).append((ts, value)) def get(self, key, ts): arr = self.store.get(key, []) l, r, ans = 0, len(arr) - 1, "" while l <= r: mid = (l + r) // 2 if arr[mid][0] <= ts: # 合法候选 ans = arr[mid][1] # 记下值，往右找更晚的 l = mid + 1 else: # 太晚，往左 r = mid - 1 return ans复杂度
- set 时间：O(1)，直接往该键的列表末尾追加一条记录
- get 时间：O(log n)，在该键的 n 条有序时间戳上二分查找
- 空间：O(总记录数)，存下所有 set 进来的 (时间戳, 值) 对
易错点
面试追问把动画讲成自己的话
追问为什么 get 能用二分？
追问set 需要排序或插入到中间吗？
追问如果某个键从没 set 过，get 返回什么？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
寻找两个正序数组的中位数
LeetCode 4 · 困难 · 沿着 二分查找 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题