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
.
这道题让实现一个 RecentCounter 类,里面有一个 ping 函数,输入给定了一个时间t,让我们求在 [t-3000, t] 时间范围内有多少次 ping。题目中限定了每次的给的时间一定会比上一次的时间大,而且只关心这个大小为 3001 的时间窗口范围内的次数,则利用滑动窗口 Sliding Window 来做就是个很不错的选择。由于数字是不断加入的,可以使用一个 queue,每当要加入一个新的时间点t时,先从队列开头遍历,若前面的时间不在当前的时间窗口内,则移除队列。之后再将当前时间点t加入,并返回队列的长度即可,参见代码如下:
class RecentCounter {
public:
RecentCounter() {}
int ping(int t) {
while (!q.empty()) {
if (q.front() + 3000 >= t) break;
q.pop();
}
q.push(t);
return q.size();
}
private:
queue<int> q;
};
Github 同步地址:
https://github.com/grandyang/leetcode/issues/933
参考资料:
https://leetcode.com/problems/number-of-recent-calls/
LeetCode All in One 题目讲解汇总(持续更新中…)
转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com