LC.981 ｜ 基于时间的键值存储 ｜ 哈希 ｜ upper_bound快速定位

输入：

• set(key, value, timestamp)
• get(key, timestamp)

要求：

• 同一个key在不同timestamp可以存多次
• get需要返回：timestamp_prev <= timestamp的最大那次对应的 value
• 如果不存在返回空串""

输出：

• set：无返回
• get：string

思路：

这题的核心就是：对每个 key，把 (timestamp -> value) 存起来，并且能快速找“<= timestamp 的最大时间点”。

数据结构选择：

• 外层：unordered_map<string, ...>通过 key 快速定位一组记录
• 内层：map<int, string>自动按 timestamp 升序存放，支持二分相关操作

get(key, timestamp)怎么找？

• 用upper_bound(timestamp)：它返回第一个 > timestamp 的迭代器
• 那么“<= timestamp 的最大值”就是它的前一个位置
• 特判两种情况：
  1. 这个 key 压根不存在 ->""
  2. upper_bound指向 begin，说明所有 timestamp 都 > 目标 ->""
  3. 否则--it返回答案

复杂度：

• 时间复杂度：
  • set：O(log M)
  • get：O(log M)
  • 其中 M 是某个 key 下存了多少条记录
• 空间复杂度：O(总记录数)

classTimeMap{unordered_map<string,map<int,string>>m;public:TimeMap(){}voidset(string key,string value,inttimestamp){m[key][timestamp]=value;}stringget(string key,inttimestamp){if(m.find(key)==m.end())return"";map<int,string>&time_m=m[key];autoit=time_m.upper_bound(timestamp);// first > timestampif(it==time_m.begin())return"";// all > timestamp--it;// last <= timestampreturnit->second;}};