933. 最近的请求次数

题目解析

这道题是让我们先写一个类，然后再实例化这个类，然后再给题目输入的数组的顺序去依次调用我们写的 ping 方法，也就是["RecentCounter", "ping", "ping", "ping", "ping"]

每次调用传进去参数的 t 就是[[], [1], [100], [3001], [3002]]

每次返回的数字都会添加到输出的数组里面，也就是[null, 1, 2, 3, 3]

解题思路

根据题目的输入输出

输入：
[[], [1], [100], [3001], [3002]]
输出：
[null, 1, 2, 3, 3]

是在 1 毫秒、100 毫秒，3001 毫秒、3002 毫秒发出请求

输出为[null, 1, 2, 3, 3]

意思是在第 1 秒内发出的请求有一个请求，在 100 毫秒有两个请求，在 3001 毫秒的时候有三个请求，因为是 3001-3000 = 1 ，但是 1 是闭区间所以也算进去了，3002 毫秒有三个请求，因为不算 1 毫秒

得到规律，发出的请求越早越不在 3000ms 内的请求里，也就是队列的先进先出

解题步骤

1. 有新请求就入队，并且把 3000ms 前发出的请求出队
2. 队列的长度就是最近的请求次数

代码

var RecentCounter = function() {
    this.queue = []
}

/**
 * @param {number} t
 * @return {number}
 */
RecentCounter.prototype.ping = function(t) {
    this.queue.push(t)
    while (this.queue[0] < t - 3000) {
        this.queue.shift()
    }
    return this.queue.length
}

/**
 * Your RecentCounter object will be instantiated and called as such:
 * var obj = new RecentCounter()
 * var param_1 = obj.ping(t)
 */

复杂度分析

时间复杂度：代码中有个 while 循环体，所以复杂度就是 O(n),n 就是请求的个数

空间复杂度：代码中有个this.queue = [],所以空间复杂度是 O(n),n 就是队列的长度，也就是题目中的最近的请求次数