第1.4篇·最近的请求次数

算法是求职的敲门砖，大厂面试一面几乎都会问算法题，以此来考察候选人的思维逻辑及编码能力。

今天要AC的题目叫做「最近的请求次数」，在 leetcode 上的原题链接为：https://leetcode-cn.com/problems/number-of-recent-calls/

1. 题目

写一个 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]，范围是 [-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 <= 10^9
• 保证每次对 ping 调用所使用的 t 值都 严格递增
• 至多调用 ping 方法 10^4 次

2. 解题思路

题目意思还是比较简单的，输入一系列数字，要求返回这些数字中大于等于 T-3000 且小于等于 T 的数字的个数。我们只需要在 RecentCounter 类中维护一个数组，用于存储输入的数字，然后每次输入数字的时候，对数组进行遍历，同时进行比较即可，把符合要求范围的数字数量返回。

需要注意的是：

• 输入数字的范围是 [1, 1000000000]，所以我们可以直接使用 int 来存储，无需担心溢出问题
• 题目保证每次对 ping 调用所使用的 t 值都 严格递增，所以在存储输入的时候自然会保持一个递增顺序，不需要手动进行排序
• 至多调用 ping 方法 10^4 次，这就要求我们在声明数组范围的时候只需要申请一个 10^4 大小的数组即可

除此之外，我们还需要在 RecentCounter 类中维护一个数组下标，它代表了下一个为空的数组下标，可以直接存储输入的数字，同时它还可以在进行循环时控制循环的结束条件为 i < index（因为数组大于 index 下标的部分并未存储内容）。

用 Java 实现上述的思路就是：

上述示例代码在 leetcode 上的执行结果是：

当然，我们还可以使用链表、栈来存储输入数字，这些解法都大同小异，这里就不做展开了。

最后，本文收录于个人语雀知识库: 我所理解的后端技术，欢迎来访。