最近的请求次数

#2024/07/28 #算法/列队

目录

• 题目及理解
• 解题思路
• 代码实现
  • 复杂度分析
• 错误记录

题目及理解

解题思路

使用列队：

1. 初始化队列：
   • 使用一个队列来存储所有请求的时间。
2. 处理每个 ping(t) 请求：
   • 将时间 t 入队。
   • 遍历：从队列的前面（即最老的请求）开始检查，如果有请求已经不在 [t-3000, t] 这个时间范围，移除它们。
   • 返回队列的长度。

代码实现

var RecentCounter = function () {
  // 使用队列来存储ping的时间
  this.q = [];
};

/**
 * @description:在时间t 时 ping了一下
 * @param {number} t
 * @return {number}
 */
RecentCounter.prototype.ping = function (t) {
  // 把当前的 t 入队
  this.q.push(t);
  // 如果队头小于 t - 3000，就删除队头，即只保留 3000 毫秒内的请求
  while (this.q[0] < t - 3000) {
    // t 是递增的，所以可以从队头删除 3000 毫秒之前的请求
    this.q.shift();
  }
  // 返回队列的长度
  return this.q.length;
};

复杂度分析

• 时间复杂度：
  • 每个请求最多只执行一次入队和一次出队操作，因此对于每个 ping请求，其操作的时间复杂度是 O(1)。
  • 综上，处理 n 个 ping 请求的总时间复杂度是 O(n)。
• 空间复杂度：
  • 队列在最坏情况下需要存储所有在时间范围 [t-3000, t] 内的请求。因此，空间复杂度是 O(n)，其中 n 是最大同时存在的请求数（理论上可看为所有请求数）

错误记录

[!danger] 每次入队后，还需要 while 遍历一遍保证每个元素都在 3000ms 内