共计 2299 个字符，预计需要花费 6 分钟才能阅读完成。
前言
Weekly Contest 121 的 基于时间的键值存储：
创建一个基于时间的键值存储类 TimeMap，它支持下面两个操作：
set(string key, string value, int timestamp)
存储键 key、值 value，以及给定的时间戳 timestamp。
get(string key, int timestamp)
返回先前调用 set(key, value, timestamp_prev) 所存储的值，其中 timestamp_prev <= timestamp。
如果有多个这样的值，则返回对应最大的 timestamp_prev 的那个值。
如果没有值，则返回空字符串（””）。
示例 1：
输入：inputs = [“TimeMap”,”set”,”get”,”get”,”set”,”get”,”get”], inputs = [[],[“foo”,”bar”,1],[“foo”,1],[“foo”,3],[“foo”,”bar2″,4],[“foo”,4],[“foo”,5]]
输出：[null,null,”bar”,”bar”,null,”bar2″,”bar2″]
解释：
TimeMap kv;
kv.set(“foo”, “bar”, 1); // 存储键 “foo” 和值 “bar” 以及时间戳 timestamp = 1
kv.get(“foo”, 1); // 输出 “bar”
kv.get(“foo”, 3); // 输出 “bar” 因为在时间戳 3 和时间戳 2 处没有对应 “foo” 的值，所以唯一的值位于时间戳 1 处（即 “bar”）
kv.set(“foo”, “bar2”, 4);
kv.get(“foo”, 4); // 输出 “bar2”
kv.get(“foo”, 5); // 输出 “bar2”
示例 2：
输入：inputs = [“TimeMap”,”set”,”set”,”get”,”get”,”get”,”get”,”get”], inputs = [[],[“love”,”high”,10],[“love”,”low”,20],[“love”,5],[“love”,10],[“love”,15],[“love”,20],[“love”,25]]
输出：[null,null,null,””,”high”,”high”,”low”,”low”]
提示：
所有的键 / 值字符串都是小写的。
所有的键 / 值字符串长度都在 [1, 100] 范围内。
所有 TimeMap.set 操作中的时间戳 timestamps 都是严格递增的。
1 <= timestamp <= 10^7
TimeMap.set 和 TimeMap.get 函数在每个测试用例中将（组合）调用总计 120000 次。
解题思路
本题解题前可以去了解一下时序数据库，本题其实就是实现一个简单的时序数据库。同时实现也是很简单：
首先定义一个 ValueMap，该 Map 以 timestamp 为 key，以 value 为 value，这样就能够记录下不同 timestamp 下的 value。
然后再定义一个 Map, 该 Map 以 key 为 key，以 ValueMap 为 value。
需要注意 ValueMap 我选择的是用 TreeMap，其提供 firstKey() 能够快速找到第一个元素，而 floorEntry() 则会返回与小于或等于给定键的最大键关联的键值映射，如果没有这样的键，则返回 null。
实现代码
/**
* 981. 基于时间的键值存储
* @author RJH
* create at 2019-01-27
*/
public class TimeMap {
/**
* 将 HashMap 和 TreeMap 组合使用
* 使用 TreeMap 是因为其能够有序的存储数据，因为其提供的 firstKey() 和 floorEntry() 很方便
*/
private HashMap<String,TreeMap<Integer,String>> map;
/** Initialize your data structure here. */
public TimeMap() {
map=new HashMap<>();
}
public void set(String key, String value, int timestamp) {
// 判断是否存在这个 Key
if(map.containsKey(key)){
TreeMap<Integer,String> valueMap=map.get(key);
// 以 timpstamp 作为 key 确保记录不同 timestamp 下的 value
valueMap.put(timestamp,value);
}else{
// 初次记录该 key，初始化 ValueMap
TreeMap<Integer,String> valueMap=new TreeMap<>();
valueMap.put(timestamp,value);
map.put(key,valueMap);
}
}
public String get(String key, int timestamp) {
if(map.containsKey(key)){
TreeMap<Integer,String> valueMap=map.get(key);
if(valueMap.containsKey(timestamp)){
return valueMap.get(timestamp);
}else{
// 需要防止输入的 timestamp 比存储的 timestamp 都要小的情况
if(timestamp<valueMap.firstKey()){
return “”;
}else{
return valueMap.floorEntry(timestamp).getValue();
}
}
}else{
return “”;
}
}
}
