前言
这是力扣的 933 题，难度为简单，解题方案有很多种，本文讲解我认为最奇妙的一种。
慢慢开始队列的模块了，这道题是一道非常好的队列的例题，很有代表性。
一、题目描述
写一个 RecentCounter 类来计算特定时间范围内最近的请求。
请你实现 RecentCounter 类：
RecentCounter()初始化计数器，请求数为 0 。int ping(int t)在时间t添加一个新请求，其中t表示以毫秒为单位的某个时间，并返回过去3000毫秒内发生的所有请求数（包括新请求）。确切地说，返回在[t-3000, t]内发生的请求数。
保证 每次对 ping 的调用都使用比之前更大的 t 值。
示例 1：
代码语言：javascript复制输入：
["RecentCounter", "ping", "ping", "ping", "ping"]
[[], [1], [100], [3001], [3002]]
输出：
[null, 1, 2, 3, 3]
解释：
RecentCounter recentCounter = new RecentCounter();
recentCounter.ping(1); // requests = [1]，范围是 [-2999,1]，返回 1
recentCounter.ping(100); // requests = [1, 100]，范围是 [-2900,100]，返回 2
recentCounter.ping(3001); // requests = [1, 100, 3001]，范围是 [1,3001]，返回 3
recentCounter.ping(3002); // requests = [1, 100, 3001, 3002]，范围是 [2,3002]，返回 3提示：
1 <= t <= 109- 保证每次对
ping调用所使用的t值都 严格递增 - 至多调用
ping方法104次
二、题解
2.1 队列问题一般解法
队列是一种特殊的线性表，只允许在表的前端进行删除操作，在表的后端进行插入操作。以下是队列问题的基本算法：
- 初始化队列：创建一个空队列，并设置一个队头指针和一个队尾指针，分别指向队列的开头和结尾。
- 入队操作：将一个元素插入到队列的尾部。具体操作是先将队尾指针向后移动一位，然后将新元素插入到队尾指针所指的位置。
- 出队操作：从队列的头部删除一个元素。具体操作是先将队头指针向后移动一位，然后返回队头指针所指向的元素。如果队列为空，则无法进行出队操作。
- 获取队头元素：返回队头指针所指向的元素，但不删除该元素。如果队列为空，则无法获取队头元素。
- 判断队列是否为空：如果队头指针和队尾指针指向同一位置，则队列为空。
以上是队列问题的基本算法，可以用于解决各种相关问题，如生产者消费者问题、约瑟夫环问题等。
2.2 方法一：队列
思路与算法：
由于每次调用 ping 方法时，请求时间 t 是严格单调递增的，因此按照调用顺序存储请求时间可以得到请求时间的严格递增序列。每次调用 ping 方法要求返回过去 3000 毫秒内发生的所有请求数，因此可以将请求时间序列中的距离请求时间超过 3000 毫秒的请求删除，然后计算请求时间序列中的请求数，即为过去 3000 毫秒内发生的所有请求数。
由于最早发生的请求会最先被删除，因此请求时间序列满足先进先出的特点，可以使用队列实现请求时间序列，在构造方法中初始化队列。
对于 ping 方法，首先将过时的请求出队列，如果队列不为空且队首元素距离当前请求时间超过 3000 毫秒，则将队首元素出队列，重复该操作直到队列变为空或者队首元素距离当前请求时间不超过 3000 毫秒。然后将当前请求时间入队列，此时队列内的元素个数即为过去 3000 毫秒内发生的所有请求数，返回队列内的元素个数即可。
三、代码
3.1 方法一：队列
Java版本：
代码语言：javascript复制class RecentCounter {
static final int RANGE = 3000;
Queue<Integer> queue;
public RecentCounter() {
queue=new ArrayDeque<>();
}
public int ping(int t) {
while(!queue.isEmpty()&&t-queue.peek()>RANGE){
queue.poll();
}
queue.add(t);
return queue.size();
}
}C 版本：
代码语言：javascript复制#include <queue>
using namespace std;
class RecentCounter {
private:
static const int RANGE = 3000;
queue<int> q;
public:
RecentCounter() {}
int ping(int t) {
while (!q.empty() && t - q.front() > RANGE) {
q.pop();
}
q.push(t);
return q.size();
}
};Python版本：
代码语言：javascript复制from collections import deque
class RecentCounter:
RANGE = 3000
def __init__(self):
self.q = deque()
def ping(self, t: int) -> int:
while self.q and t - self.q[0] > self.RANGE:
self.q.popleft()
self.q.append(t)
return len(self.q)Go版本：
代码语言：javascript复制package main
import "container/list"
type RecentCounter struct {
rangeVal int
q *list.List
}
func Constructor() RecentCounter {
return RecentCounter{rangeVal: 3000, q: list.New()}
}
func (this *RecentCounter) Ping(t int) int {
for this.q.Len() > 0 && t-this.q.Front().Value.(int) > this.rangeVal {
this.q.Remove(this.q.Front())
}
this.q.PushBack(t)
return this.q.Len()
}四、复杂度分析
4.1 方法一：队列
- 时间复杂度 ：构造方法的时间复杂度是 O(1)，方法 ping 的均摊时间复杂度是 O(1)。每个元素最多入队和出队各一次，因此方法 ping 的均摊时间复杂度是 O(1)。
- 空间复杂度：O(n)，其中 n 是请求次数。空间复杂度主要取决于队列空间，队列内存储最近 3000毫秒的请求，空间复杂度是 O(n)。
