写一个 RecentCounter
类来计算特定时间范围内最近的请求。
请实现 RecentCounter
类:
RecentCounter()
初始化计数器,请求数为 0 。
int ping(int t)
在时间 t
添加一个新请求,其中 t
表示以毫秒为单位的某个时间,并返回过去 3000
毫秒内发生的所有请求数(包括新请求)。确切地说,返回在 [t-3000, t]
内发生的请求数。
保证 每次对 ping
的调用都使用比之前更大的 t
值。
示例:
**输入:**
inputs = ["RecentCounter", "ping", "ping", "ping", "ping"]
inputs = [[], [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 <= 109
- 保证每次对
ping
调用所使用的 t
值都 严格递增
- 至多调用
ping
方法 104
次
注意:本题与主站 933 题相同: https://leetcode-cn.com/problems/number-of-recent-calls/
方法一:队列
我们可以用一个队列维护发生请求的时间,当在时间 t 收到请求时,将时间 t 入队。
由于每次收到的请求的时间都比之前的大,因此从队首到队尾的时间值是单调递增的。当在时间 t 收到请求时,为了求出 [t-3000,t] 内发生的请求数,我们可以不断从队首弹出早于 t-3000 的时间。循环结束后队列的长度就是 [t-3000,t] 内发生的请求数。
[sol1-Python3]1 2 3 4 5 6 7 8 9
| class RecentCounter: def __init__(self): self.q = deque()
def ping(self, t: int) -> int: self.q.append(t) while self.q[0] < t - 3000: self.q.popleft() return len(self.q)
|
[sol1-C++]1 2 3 4 5 6 7 8 9 10 11 12 13
| class RecentCounter { queue<int> q; public: RecentCounter() {}
int ping(int t) { q.push(t); while (q.front() < t - 3000) { q.pop(); } return q.size(); } };
|
[sol1-Java]1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| class RecentCounter { Queue<Integer> queue;
public RecentCounter() { queue = new ArrayDeque<Integer>(); }
public int ping(int t) { queue.offer(t); while (queue.peek() < t - 3000) { queue.poll(); } return queue.size(); } }
|
[sol1-C#]1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| public class RecentCounter { Queue<int> queue;
public RecentCounter() { queue = new Queue<int>(); }
public int Ping(int t) { queue.Enqueue(t); while (queue.Peek() < t - 3000) { queue.Dequeue(); } return queue.Count; } }
|
[sol1-Golang]1 2 3 4 5 6 7 8 9 10 11
| type RecentCounter []int
func Constructor() (_ RecentCounter) { return }
func (q *RecentCounter) Ping(t int) int { *q = append(*q, t) for (*q)[0] < t-3000 { *q = (*q)[1:] } return len(*q) }
|
[sol1-C]1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29
| typedef struct { int *queue; int capability; int head; int tail; } RecentCounter;
RecentCounter* recentCounterCreate() { RecentCounter *obj = (RecentCounter *)malloc(sizeof(RecentCounter)); obj->capability = 10001; obj->queue = (int *)malloc(sizeof(int) * obj->capability); obj->head = 0; obj->tail = 0; return obj; }
int recentCounterPing(RecentCounter* obj, int t) { obj->queue[obj->tail++] = t; while (obj->queue[obj->head] < t - 3000) { obj->head++; } return obj->tail - obj->head; }
void recentCounterFree(RecentCounter* obj) { free(obj->queue); free(obj); }
|
[sol1-JavaScript]1 2 3 4 5 6 7 8 9 10 11
| var RecentCounter = function() { this.queue = []; };
RecentCounter.prototype.ping = function(t) { this.queue.push(t); while (this.queue[0] < t - 3000) { this.queue.shift(); } return this.queue.length; };
|
复杂度分析