🍥

Hang Zhang

genius.

Data Structure and Algorithm

Number of Recent Calls

933. 最近的请求次数

分析

利用队列的先进先出特性来存储请求的时间点，并维护一个滑动窗口：

存储请求时间：
- 每次调用 ping(t)，将时间 t 加入队列
移除过期请求：
- 从队列头部开始检查，如果某个时间点不在 [t-3000, t] 范围内（即 t - q.front() > 3000），则将其从队列中移除
统计有效请求：
- 最后，队列的大小即为过去 3000 毫秒内的请求数量

时间复杂度

时间复杂度 O(1)

空间复杂度

空间复杂度为 O(n)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class RecentCounter
{
public:
    std::queue<int> q; // 用于存储请求时间点的队列

    RecentCounter()
    {
        // 构造函数初始化，无需额外操作
    }

    int ping(int t)
    {
        q.push(t); // 将当前请求时间添加到队列
        // 移除不在 [t-3000, t] 范围内的请求
        while (t - q.front() > 3000)
            q.pop();
        return q.size(); // 返回队列大小，即为有效请求数
    }
};