933.最近的请求次数

最近的请求次数

写一个 RecentCounter 类来计算特定时间范围内最近的请求。

请你实现 RecentCounter 类：

• RecentCounter() 初始化计数器，请求数为 0
• int ping(int t) 在时间 t 添加一个新请求，其中 t 表示以毫秒为单位的当前时间，并返回过去 3000 毫秒内发生的请求数（包括新请求）。

示例 1:

输入：[“RecentCounter”, “ping”, “ping”, “ping”, “ping”]
[[], [1], [100], [3001], [3002]]
输出：[null, 1, 2, 3, 3]

提示:

• 1 <= t <= 10^9
• 保证每次调用 ping 都使用比之前更大的 t 值
• 最多调用 ping 10^4 次

解析

使用队列保存请求时间，ping 时移除超过 3000 毫秒的请求，返回队列长度。

var RecentCounter = function () {
  this.queue = [];
};

RecentCounter.prototype.ping = function (t) {
  this.queue.push(t);
  while (this.queue[0] < t - 3000) {
    this.queue.shift();
  }
  return this.queue.length;
};

时间复杂度 O(n)，空间复杂度 O(n)。