你好，同学！欢迎来到 NOI 数据结构专题训练。

今天我们要研究的是最近的请求次数。这道题虽然在 LeetCode 上是一道简单题，但在 NOI 竞赛中，它代表了一类非常重要的算法模型：基于时间顺序的滑动窗口（Sliding Window）。通过这道题，你可以深刻理解**队列（Queue）**如何高效处理“过期数据”。

一、 预备知识点

在挑战本题前，请确保你已经掌握：

1. 队列（Queue）：先进先出（FIFO）的线性结构。
2. 滑动窗口思想：维护一个区间，随着区间的移动，动态地移出左侧不再需要的元素，加入右侧新元素。
3. C++ STL std::queue：
   • push(x)：入队。
   • pop()：出队。
   • front()：查看队首。
   • size()：获取队列长度。

二、 NOI 竞赛题目描述

题目名称：最近的请求次数 (Number of Recent Calls) 时间限制：1.0s 内存限制：256MB

【问题描述】 写一个 RecentCounter 类来计算特定时间范围内最近的请求。 请你实现 RecentCounter 类：

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

注意：保证每次对 ping 的调用都使用比之前更大的 t 值（即 t 是严格递增的）。

【输入格式】 第一行包含一个整数 $N$，表示调用 ping 的次数。 接下来的 $N$ 行，每行包含一个整数 $t$，表示当前请求的时间戳。

【输出格式】 对于每个 $t$，输出一个整数，表示返回的请求数，每个结果占一行。

【样例输入】

4
1
100
3001
3002

【样例输出】

1
2
3
3

【数据规模与约定】

• $1 \le N \le 10^4$
• $1 \le t \le 10^9$
• 保证每次调用的 $t$ 都是严格递增的。

三、 启发式思路引导：草稿纸上的推演

请拿出草稿纸，我们画一条时间轴来模拟：

1. 核心矛盾：如何快速定位“过期的请求”？

• 观察：由于 $t$ 是严格递增的，较早进来的请求一定会比后进来的请求先“过期”。
• 特性：先进来的先处理（检查并删除），这完全符合队列的特性。

2. 草稿纸模拟过程

假设窗口大小为 3000 毫秒：

1. ping(1)：队列放入 1。窗口范围 (-2999, 1)。队列：(1)。返回 1。
2. ping(100)：队列放入 100。窗口范围 (-2900, 100)。队首 1 在范围内。队列：(1, 100)。返回 2。
3. ping(3001)：队列放入 3001。窗口范围 (1, 3001)。检查队首：1 在范围内。队列：(1, 100, 3001)。返回 3。
4. ping(3002)：队列放入 3002。窗口范围 (2, 3002)。
   • 检查队首 1：小于 2，已过期！弹出。
   • 检查队首 100：大于 2，有效。
   • 队列：(100, 3001, 3002)。返回 3。

四、 复杂度分析与时间复杂度优化建议

• 时间复杂度：
  • 单次 ping 操作：虽然内部有一个 while 循环，但每个元素一生只会被 push 一次，pop 一次。
  • 均摊复杂度（Amortized Analysis）：单次 ping 的均摊时间复杂度为 $O(1)$。
  • 总时间复杂度为 $O(N)$。
• 空间复杂度：$O(W)$，其中 $W$ 是窗口内最多可能存在的请求数。最坏情况下为 $O(N)$。

优化建议： 在 NOI 中，如果 $N$ 达到 $10^6$ 级别，std::queue 的动态内存分配可能略慢。可以使用一个大数组模拟循环队列，通过头尾指针（head, tail）来进一步压低常数时间。

五、 算法流程图（伪代码逻辑）

在流程图中，我们使用通俗描述替代特殊符号。

graph TD
    Start(开始处理 Ping 时间 t) --> Push(将时间 t 压入队列尾部)
    Push --> Check{队列是否不为空}
    Check -- 是 --> TimeLimit(计算失效时间阈值 limit 等于 t 减 3000)
    TimeLimit --> Condition{队首元素是否小于 limit}
    Condition -- 是 --> Pop(弹出队首过期元素)
    Pop --> Check
    Condition -- 否 --> Return(返回队列当前的 size)
    Check -- 否 --> Return
    Return --> End(Ping 操作结束)

六、 读题关键词总结

在 NOI 竞赛中，遇到此类题目请圈出以下关键词：

1. “严格递增” (Strictly Increasing)：这是使用单调队列或普通队列维护滑动窗口的金标准。它意味着你不需要重新排序，队列里的顺序天然就是时间顺序。
2. “过去 X 毫秒内” (Recent / Window)：这提示你需要维护一个范围，即滑动窗口。
3. “返回请求数”：通常对应队列的长度。

教练寄语： 这道题的核心是**“垃圾清理”**。队列不仅是用来存数据的，更是用来有序地丢弃废弃数据的。当你能熟练处理这种“随时间推移而失效”的数据时，你就迈入了处理实时数据流的大门。去实现它吧！