**Problem**

Write a class `RecentCounter`

to count recent requests.

It has only one method: `ping(int t)`

, where t represents some time in milliseconds.

Return the number of `ping`

s that have been made from 3000 milliseconds ago until now.

Any ping with time in `[t - 3000, t]`

will count, including the current ping.

It is guaranteed that every call to `ping`

uses a strictly larger value of `t`

than before.

**Example 1:**

Input:inputs = ["RecentCounter","ping","ping","ping","ping"], inputs = [[],[1],[100],[3001],[3002]]Output:[null,1,2,3,3]

**Note:**

- Each test case will have at most
`10000`

calls to`ping`

. - Each test case will call
`ping`

with strictly increasing values of`t`

. - Each call to ping will have
`1 <= t <= 10^9`

.

# Solution: Queue

Use a FIFO queue to track all the previous pings that are within 3000 ms to current.

Time complexity: Avg O(1), Total O(n)

Space complexity: O(n)

## C++

1 2 3 4 5 6 7 8 9 10 11 12 |
class RecentCounter { public: RecentCounter() {} int ping(int t) { while (!q.empty() && t - q.front() > 3000) q.pop(); q.push(t); return q.size(); } private: queue<int> q; }; |