头脑风暴之最近的请求次数

头脑风暴之最近的请求次数

题目：

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

请你实现 RecentCounter 类：

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

示例:

输入：["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]，返回 1recentCounter.ping(100); // requests = [1, 100]，范围是 [-2900,100]，返回 2recentCounter.ping(3001); // requests = [1, 100, 3001]，范围是 [1,3001]，返回 3recentCounter.ping(3002); // requests = [1, 100, 3001, 3002]，范围是 [2,3002]，返回 3

解决思路

题目意思就是往队列里存放元素啊，每次ping就存一个数，然后存的时候看一下之前的数是否在t-3000之外了，是就删除；

比如题目给的例子：

输入： ["RecentCounter", "ping", "ping", "ping", "ping"] [[], [1], [100], [3001], [3002]] 输出： [null, 1, 2, 3, 3] 就是第一次存个1，第二次存个100……

然后每次存的时候，看看之前存的元素，有多少个在这次存的 t 到t-3000之间；

存1的时候，1在[-2999,1]之间，就这一个数，所以说返回数目1； ……

存3002的时候就删除1，因为1不在[2,3002]之间，而100，3001，3002都是在[2,3002]之间，就返回数目3；

代码实现

class RecentCounter { Queue q; public RecentCounter() { q = new LinkedList(); } public int ping(int { q.add(t); while (q.peek() < t - 3000) { q.poll(); } return

最后

时间复杂度：O(Q)，其中 QQ 是 ping 的次数。空间复杂度：O(W)，其中 W = 3000 是队列中最多存储的 ping 的记录数目。

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。