题目内容

请实现一个带容量上限和过期时间的缓存。

• capacity：最多同时存放多少个不同的键
• 每个键对应一个值，以及一个过期时刻 expireAt

在时刻 now 判断是否过期的规则是：若 $now \ge \textit{expireAt}$，则该键已过期（expireAt 表示「从这个时刻起失效」）。

注意：过期键在调用 purge 之前仍占容量；get 遇到过期键只返回 -1，不会自动删除。

需要实现的接口

• TTLCache(int capacity)：初始化空缓存（保证 $capacity \ge 1$）
• put(int key, int value, int expireAt)：写入或覆盖该键的值与过期时刻
  • 若写入后键的个数超过 capacity：淘汰一个键——优先淘汰 expireAt 最小者；若并列，淘汰 key 更小者
  • 不顺便清理其它已过期键；无返回值
• get(int key, int now)：
  • 键不存在，或已过期（$now \ge \textit{expireAt}$）→ 返回 -1
  • 否则返回对应的值
  • 不改变缓存里存了哪些键
• purge(int now)：删除所有满足 $now \ge \textit{expireAt}$ 的键，返回删除个数
• size()：返回当前存放的键数量（包含已过期但尚未 purge 的键）

输入描述

每行一次函数调用。首行 TTLCache(capacity)。累计调用不超过 $4000$ 次。

• $1 \le \textit{capacity} \le 500$
• $-10^6 \le \textit{key},\textit{value} \le 10^6$
• $0 \le \textit{expireAt},\textit{now} \le 10^9$

输出描述

• 构造 / put 返回 null
• get / purge / size 返回整数

样例1

输入：

TTLCache(2)
put(1, 10, 5)
put(2, 20, 3)
get(2, 2)
get(2, 3)
put(3, 30, 4)
get(1, 0)
size()
purge(4)
size()
get(3, 4)

输出：

null
null
null
20
-1
null
10
2
1
1
-1

说明：

• put(1,10,5)、put(2,20,3)：缓存满 $2$ 个键
• get(2,2)：未过期，返回 $20$
• get(2,3)：$3\ge 3$ 已过期，返回 -1，但键 2 仍占位
• put(3,30,4)：超容量，按过期时刻淘汰最早的键 2（expireAt=3），留下 {1,3}
• get(1,0) 仍命中；$size()=2$
• purge(4)：删去已过期的 3（$4\ge 4$），返回 $1$；剩键 1，$size()=1$
• get(3,4)：键已不存在，返回 -1