933. 最近的请求次数

🟢   🔖  设计 队列 数据流  🔗 力扣 LeetCode

题目

You have a RecentCounter class which counts the number of recent requests within a certain time frame.

Implement the RecentCounter class:

• RecentCounter() Initializes the counter with zero recent requests.
• int ping(int t) Adds a new request at time t, where t represents some time in milliseconds, and returns the number of requests that has happened in the past 3000 milliseconds (including the new request). Specifically, return the number of requests that have happened in the inclusive range [t - 3000, t].

It is guaranteed that every call to ping uses a strictly larger value of t than the previous call.

Example 1:

Input

["RecentCounter", "ping", "ping", "ping", "ping"]

[[], [1], [100], [3001], [3002]]

Output

[null, 1, 2, 3, 3]

Explanation

RecentCounter recentCounter = new RecentCounter();
recentCounter.ping(1); // requests = [1], range is [-2999,1], return 1
recentCounter.ping(100);   // requests = [1 , 100], range is [-2900,100], return 2
recentCounter.ping(3001);  // requests = [1 , 100 , 3001], range is [1,3001], return 3
recentCounter.ping(3002);  // requests = [1, 100 , 3001 , 3002], range is [2,3002], return 3

Constraints:

• 1 <= t <= 10^9
• Each test case will call ping with strictly increasing values of t.
• At most 10^4 calls will be made to ping.

题目大意

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

请你实现 RecentCounter 类：

• RecentCounter() 初始化计数器，请求数为 0 。
• int ping(int t) 在时间 t 添加一个新请求，其中 t 表示以毫秒为单位的某个时间，并返回过去 3000 毫秒内发生的所有请求数（包括新请求）。确切地说，返回在 [t-3000, t] 内发生的请求数。

保证 每次对 ping 的调用都使用比之前更大的 t 值。

示例 1：

输入：

["RecentCounter", "ping", "ping", "ping", "ping"]

[[], [1], [100], [3001], [3002]]

输出：

[null, 1, 2, 3, 3]

解释：

RecentCounter recentCounter = new RecentCounter();
recentCounter.ping(1); // requests = [1], range is [-2999,1], return 1
recentCounter.ping(100);   // requests = [1 , 100], range is [-2900,100], return 2
recentCounter.ping(3001);  // requests = [1 , 100 , 3001], range is [1,3001], return 3
recentCounter.ping(3002);  // requests = [1, 100 , 3001 , 3002], range is [2,3002], return 3

提示：

• 1 <= t <= 10^9
• 保证每次对 ping 调用所使用的 t 值都 严格递增
• 至多调用 ping 方法 10^4 次

解题思路

1. 属性初始化：RecentCounter 类包含一个数组 requests，用于存储所有请求的时间戳。

2. ping 方法：

   • ping 方法在收到一个新请求时，将当前请求时间戳 t 记录在 requests 数组中，并移除所有在当前时间 t 的 3000 毫秒前的请求（即小于 t - 3000 的请求）。
   • while 循环逐一检查 requests 的开头元素（即最早的请求时间），如果小于 t - 3000，则从队列的头部移除该元素，直到只剩下在最近 3000 毫秒内的请求。
   • 最后，返回当前队列的长度，即 3000 毫秒内的请求数量。

复杂度分析

• 时间复杂度：O(n)，其中 n 为 requests 中的请求数量，最坏情况下，每次 ping 操作都需要移除旧请求。
• 空间复杂度：O(n)，存储最近 3000 毫秒内的请求数量。

代码

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

/**
 * @param {number} t
 * @return {number}
 */
RecentCounter.prototype.ping = function (t) {
	while (this.requests.length > 0 && this.requests[0] < t - 3000) {
		// 移除所有超过 3000 毫秒的旧请求
		this.requests.shift();
	}
	// 添加当前请求时间戳
	this.requests.push(t);
	// 返回 3000 毫秒内的请求数量
	return this.requests.length;
};