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 toping
. - Each test case will call
ping
with strictly increasing values oft
. - 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; }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment