933. 最近的请求次数

🎯 问题描述

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

请你实现 RecentCounter 类：

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

说明：

这是一个队列与滑动窗口结合的问题。
核心策略：
- 每次调用 ping(t) 时，相当于时间窗口的右边界移动到了 t。
- 我们需要维护队列，使得队列中只保留 [t-3000, t] 范围内的请求时间戳。
- 利用队列“先进先出”的特性，将超出左边界（小于 t-3000）的旧请求从队首移除。
- 最终队列的长度就是当前时间窗口内的请求次数。
示例：
示例 1：

输入：
["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：队列 + 滑动窗口

核心逻辑

初始化：
- 在 __init__ 中创建一个双端队列 deque，用于存储请求的时间戳。
处理请求 ping(t)：
- 计算左边界：当前有效时间窗口的左边界为 l = t - 3000。
- 移除过期请求：检查队首元素（最早的请求），如果它小于左边界 l，说明它已经超出了 [t-3000, t] 的范围，将其从队首弹出 (popleft())。重复此步骤直到队首元素在范围内或队列为空。
- 添加新请求：将当前时间 t 加入队尾 (append(t))。
- 返回结果：返回当前队列的长度，即为有效请求的数量。

代码实现

from collections import deque

class RecentCounter:
    def __init__(self):
        # 初始化一个双端队列，用于存储请求的时间戳
        self.q = deque()

    def ping(self, t: int) -> int:
        # 计算当前时间窗口的左边界
        l = t - 3000
        
        # 移除所有早于左边界的过期请求
        # 因为题目保证 t 严格递增，所以过期的请求一定在队首
        while self.q and self.q[0] < l:
            self.q.popleft()
            
        # 将当前请求时间加入队尾
        self.q.append(t)
        
        # 返回队列长度，即 [t-3000, t] 范围内的请求数
        return len(self.q)

📊 性能分析

时间复杂度：均摊 $O(1)$ $O (1)$
- 虽然代码中有 while 循环，但每个时间戳 t 最多只会入队一次、出队一次。因此，对于 n 次 ping 调用，总的时间复杂度是 $O(n)$ ，平均每次调用的时间复杂度为 $O(1)$ 。
空间复杂度： $O(W)$ $O (W)$
- 其中 $W$ 是时间窗口内能容纳的最大请求数。队列中最多存储 [t-3000, t] 范围内的所有请求。

思考

为什么使用队列？
- 题目要求统计“过去 3000 毫秒内”的请求，这天然符合“先进先出”的逻辑。最早发生的请求会最早过期，队列的队首正好对应时间轴上最早的请求，非常适合用来维护滑动窗口。
t 严格递增的重要性：
- 题目保证每次调用 ping 的 t 值都比之前大。这意味着请求时间戳在队列中是单调递增的。
- 这保证了我们只需要检查队首元素是否过期即可。如果队首元素在范围内，那么队列中后面的元素一定也在范围内，无需遍历整个队列。
与“栈”的区别：
- 如果用栈（后进先出），我们只能快速访问最新的请求，但无法快速移除最早过期的请求（它们在栈底）。队列的 popleft() 操作完美解决了移除最早元素的需求。
边界情况：
- 当 t 很小（例如 t=1）时，t-3000 为负数。由于题目保证 t >= 1，所有历史请求的时间戳都是正数，自然都大于负数左边界，因此不需要特殊处理负数边界。