最近的请求次数（阿里）
解题思路：
-
用一个队列维护发生请求的时间，当在时间 t 收到请求时，将时间 t 入队；
-
由于每次收到的请求的时间都比之前的大，因此从队首到队尾的时间值是单调递增的；
- 当在时间 t 收到请求时，为了求出 [t-3000,t] 内发生的请求数，可以不断从队首弹出早于 t−3000 的时间；
- 循环结束后队列的长度就是 [t−3000,t] 内发生的请求数；
复杂度：
-
时间复杂度：均摊 O(1)，每个元素至多入队出队各一次；
-
空间复杂度：O(L)，其中 L 为队列的最大元素个数；
代码实现：
TS
JS
class RecentCounter {
arr: Array<number>;
constructor() {
this.arr = [];
}
ping(t: number): number {
this.arr.push(t);
while (this.arr[0] < t - 3000) {
this.arr.shift();
}
return this.arr.length;
}
}
var RecentCounter = function () {
this.arr = []
};
RecentCounter.prototype.ping = function (t) {
this.arr.push(t)
while (this.arr[0] < t - 3000) {
this.arr.shift()
}
return this.arr.length
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
limit 并发请求（字节）
上一篇
评论
