Time Based Key-Value Store（基于时间的键值存储）

题目 / Problem

中文： 设计一个基于时间的键值数据结构。它能够在不同时间戳下为同一个键保存多个值，并查询指定时间对应的值。

实现 TimeMap 类：

TimeMap()：初始化数据结构。
set(key, value, timestamp)：在给定的 timestamp 下保存键 key 和值 value。
get(key, timestamp)：返回满足 timestamp_prev <= timestamp 的记录中，时间戳最大的那条记录所对应的值。如果不存在，返回空字符串 ""。

English: Design a time-based key-value data structure that stores multiple values for the same key at different timestamps and retrieves the appropriate value for a given timestamp.

Implement the TimeMap class:

TimeMap() initializes the data structure.
set(key, value, timestamp) stores value for key at the given timestamp.
get(key, timestamp) returns the value whose stored timestamp is the largest timestamp satisfying timestamp_prev <= timestamp. Return "" if no such value exists.

示例 / Example

Input:
["TimeMap", "set", "get", "get", "set", "get", "get"]
[[], ["foo", "bar", 1], ["foo", 1], ["foo", 3],
 ["foo", "bar2", 4], ["foo", 4], ["foo", 5]]

Output:
[null, null, "bar", "bar", null, "bar2", "bar2"]

const timeMap = new TimeMap();

timeMap.set("foo", "bar", 1);
timeMap.get("foo", 1); // "bar"
timeMap.get("foo", 3); // "bar"

timeMap.set("foo", "bar2", 4);
timeMap.get("foo", 4); // "bar2"
timeMap.get("foo", 5); // "bar2"

时间戳 3 没有对应的记录，因此查询 get("foo", 3) 时返回时间戳 1 对应的最近值 "bar"。
There is no record at timestamp 3, so get("foo", 3) returns the nearest earlier value "bar" stored at timestamp 1.

约束 / Constraints

1 <= key.length, value.length <= 100
key 和 value 只包含小写英文字母和数字。
key and value contain only lowercase English letters and digits.
1 <= timestamp <= 10^7
所有 set 操作的 timestamp 严格递增。
Timestamps passed to set are strictly increasing.
set 和 get 的调用次数最多为 2 × 10^5。
At most 2 × 10^5 calls are made to set and get.

解题思路：哈希表 + 二分查找 / Approach: Hash Map + Binary Search

使用 Map 按键保存历史记录：
Use a Map to store the history for each key:

key → [[timestamp, value], [timestamp, value], ...]

例如：
For example:

"foo" → [[1, "bar"], [4, "bar2"], [8, "bar3"]]

由于 set 的时间戳严格递增，每次直接把新记录追加到数组末尾，数组天然按时间升序排列，不需要重新排序。
Because timestamps passed to set are strictly increasing, each new record can be appended. Every history array remains sorted without additional sorting.

执行 get 时，需要在有序数组中查找：
For get, search the sorted history for:

最后一个 timestamp <= 查询 timestamp 的记录
the last record whose stored timestamp <= the query timestamp

这正是二分查找可以高效完成的任务。
This is exactly what binary search can find efficiently.

二分查找边界 / Binary Search Boundary

使用闭区间 [left, right] 搜索，并用 answer 保存当前找到的最优下标：
Search over the closed interval [left, right], using answer to store the best index found so far:

如果 records[mid][0] <= timestamp，当前记录可以作为答案，但右侧可能还有更接近查询时间的记录，所以令 left = mid + 1。
If records[mid][0] <= timestamp, it is a valid candidate, but a later valid record may exist, so set left = mid + 1.
如果 records[mid][0] > timestamp，时间太晚，需要向左搜索，令 right = mid - 1。
If records[mid][0] > timestamp, it is too late, so search left with right = mid - 1.

搜索结束后：
After the search:

answer === -1：不存在符合条件的记录，返回 ""。
answer === -1: no valid record exists, so return "".
否则返回 records[answer][1]。
Otherwise, return records[answer][1].

JavaScript 实现 / JavaScript Implementation

class TimeMap {
  constructor() {
    /** @type {Map<string, Array<[number, string]>>} */
    this.store = new Map();
  }

  /**
   * @param {string} key
   * @param {string} value
   * @param {number} timestamp
   * @return {void}
   */
  set(key, value, timestamp) {
    if (!this.store.has(key)) {
      this.store.set(key, []);
    }

    this.store.get(key).push([timestamp, value]);
  }

  /**
   * @param {string} key
   * @param {number} timestamp
   * @return {string}
   */
  get(key, timestamp) {
    const records = this.store.get(key);

    if (records === undefined) {
      return "";
    }

    let left = 0;
    let right = records.length - 1;
    let answer = -1;

    while (left <= right) {
      const mid = left + Math.floor((right - left) / 2);
      const storedTimestamp = records[mid][0];

      if (storedTimestamp <= timestamp) {
        answer = mid;
        left = mid + 1;
      } else {
        right = mid - 1;
      }
    }

    return answer === -1 ? "" : records[answer][1];
  }
}

/**
 * Your TimeMap object will be instantiated and called as such:
 * const obj = new TimeMap();
 * obj.set(key, value, timestamp);
 * const result = obj.get(key, timestamp);
 */

执行过程 / Walkthrough

假设保存的数据为：
Suppose the stored history is:

"foo" → [[1, "bar"], [4, "bar2"], [8, "bar3"]]

查询 get("foo", 6)：
For get("foo", 6):

`left`	`right`	`mid`	时间戳 / Stored timestamp	操作 / Action
0	2	1	4	`4 <= 6`，记录答案并向右搜索 / Save and search right
2	2	2	8	`8 > 6`，向左搜索 / Search left

最终 answer = 1，因此返回时间戳 4 对应的 "bar2"。
The final answer is 1, so return "bar2", which was stored at timestamp 4.

为什么不用线性查找？ / Why Not Use Linear Search?

从数组末尾向前查找虽然实现简单，但最坏情况下每次 get 都需要检查该键的全部历史记录。调用次数最多为 2 × 10^5，线性查询可能很慢。
Scanning backward is simple, but in the worst case every get examines the entire history for that key. With up to 2 × 10^5 operations, this can be inefficient.

利用记录已经按时间戳排序的性质，二分查找能把每次查询降为对数时间。
By using the timestamp ordering, binary search reduces each query to logarithmic time.

复杂度 / Complexity

设某个键已经保存了 m 条历史记录。
Let a particular key have m stored records.

set 时间 / Time: O(1)，直接追加到数组末尾。
Append directly to the end of the history array.
get 时间 / Time: O(log m)，对该键的历史记录进行二分查找。
Binary-search the history for that key.
空间复杂度 / Space: O(n)，其中 n 是全部 set 操作保存的记录总数。
O(n), where n is the total number of records stored by all set calls.

易错点 / Common Pitfalls

查询目标是“不大于给定时间戳的最大时间戳”，不是必须恰好等于查询时间。
Find the largest stored timestamp not exceeding the query, not only an exact match.
找到合法时间戳后仍要继续向右搜索，寻找更大的合法时间戳。
After finding a valid timestamp, continue searching right for a later valid one.
如果键不存在，或者查询时间早于该键的第一条记录，应返回 ""。
Return "" if the key is absent or the query precedes its first record.
Map.prototype.get() 可能返回 undefined，使用记录前应先检查。
Map.prototype.get() may return undefined, so check before using the records.
时间戳严格递增使数组天然有序；不要在每次 set 后重复排序。
Strictly increasing timestamps keep arrays sorted, so do not sort after every set.

Time Based Key-Value Store