算法队列之最近请求次数

题目：

写一个 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]，返回 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      

解决思路

题目意思就是往队列里存放元素啊，每次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<Integer> q;
    public RecentCounter() {
        q = new LinkedList();
    }

    public int ping(int t) {
        q.add(t);
        while (q.peek() < t - 3000) {
            q.poll();
        }
        return q.size();
    }
}      

最后

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

• ​​# UE4：来为我们的角色制作一个血条吧​​
• ​​使用 Google Breakpad 来助力解决程序崩溃​​
• ​​UE4 多人游戏服务器探索​​
• ​​使用虚幻引擎自动化工具实现自动化部署​​
• ​​如何在 UE4 中制作一扇自动开启的大门​​
• ​​如何在 UE4 中用代码去控制角色移动​​
• ​​如何给 UE4 场景添加游戏角色​​
• ​​UE4：Android 平台开发实践指南​​
• ​​UE4 开发避坑指南（持续更新）​​
• ​​新年开工啦，放个小烟花庆祝一下​​
• ​​聊聊与苹果审核员的爱恨情仇(下)​​
• ​​聊聊与苹果审核员的爱恨情仇(上)​​
• ​​一名普通工具人的 2021 | 2021年终总结​​
• ​​二叉树刷题总结：二叉搜索树的属性​​
• ​​二叉树总结：二叉树的属性​​
• ​​二叉树总结：二叉树的修改与构造​​
• ​​StoreKit2 有这么香？嗯，我试过了，真香​​
• ​​看完这篇文章，再也不怕面试官问我如何构造二叉树啦！​​
• ​​那帮做游戏的又想让大家氪金，太坏了！​​
• ​​手把手带你撸一个网易云音乐首页 | 适配篇​​
• ​​手把手带你撸一个网易云音乐首页（三）​​
• ​​手把手带你撸一个网易云音乐首页（二）​​
• ​​手把手带你撸一个网易云音乐首页（一）​​
• ​​代码要写注释吗？写你就输了​​
• ​​Codable发布这么久我就不学，摸鱼爽歪歪，哎~就是玩儿​​
• ​​iOS 优雅的处理网络数据，你真的会吗？不如看看这篇​​
• ​​UICollectionView 自定义布局！看这篇就够了​​

1. 关注公众号--- HelloWorld杰少