32 Number of Recent Calls

题目

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 pings 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.

分析

题意：传入毫秒数t的数组（那个inputs=[“RecnetCounter”]我没搞明白是干啥的）。t表示的是：当前进行ping请求时的时刻。 查询每个最近3000ms内的请求个数（如果当前3000ms已过，则重新计数）。

inputs = [[],[1],[100],[3001],[3002]]意思是，在1ms，100ms，3001ms和3002ms各发送了一个请求。 从第一个正式请求：1ms开始计时，3000ms内也就是3000+1ms，因此3000ms内的请求包括[],[1],[100],[3001]

所以算法就是：固定第一个时刻t0，然后如果后面进来的ping请求时刻在t0+3000内，那就让请求数目+1.如果时刻已经累计了3000ms，那么将当前时刻作为第一个时刻，重复操作。

由于整个请求过程是类，因此我们需要用集合存储。 由于我们需要随时跟第一个时刻进行对比，因此需要选择随时获取第一个元素的集合。 由于存在周而复始的出和入，显然，我们可以使用队列。

举例： [[],[642],[1849],[4921],[5936],[5957]] 642为初始时刻，size=1 1849<=642+3000，因此此时size=2 4921>642+3000，因此此时size重置为1 5936<=4921+3000，此时size2 5957<=4921+3000，此时size=3 答案为[1,2,1,2,3]

解答

前置知识：Java的队列

offer，add 区别：

一些队列有大小限制，因此如果想在一个满的队列中加入一个新项，多出的项就会被拒绝。

这时新的 offer 方法就可以起作用了。它不是对调用 add() 方法抛出一个 unchecked 异常，而只是得到由 offer() 返回的 false。

poll，remove 区别：

remove() 和 poll() 方法都是从队列中删除第一个元素。remove() 的行为与 Collection 接口的版本相似， 但是新的 poll() 方法在用空集合调用时不是抛出异常，只是返回 null。因此新的方法更适合容易出现异常条件的情况。

peek，element区别：

element() 和 peek() 用于在队列的头部查询元素。与 remove() 方法类似，在队列为空时， element() 抛出一个异常，而 peek() 返回 null。

官方答案

class RecentCounter {
    Queue<Integer> q;
    public RecentCounter() {
        q = new LinkedList();
    }

    public int ping(int t) {
        q.add(t);
        while (q.peek() < t - 3000)
            q.poll();
        return q.size();
    }
}