【LeetCode】三、队列相关：最近的请求次数

1、队列结构

先进先出

时间复杂度：

Java中，LinkedList集合可以当一个队列来用：

2、leetcode933：最近的请求次数

很逆天的题目描述，就是不同时间会有请求发来，现在需要计算t-3000和t闭区间之内的请求次数。

比如下面，1ms、100ms的时候分别进来两个请求，此时返回2，3001的时候再进来一个请求，[3001-3000，3001]的请求数量为3，3002的时候再进来一个请求，[3002-3000，3002]区间，1ms的请求就不算了，返回3

思路：用一个队列，每进来一个请求（或者说每入队一个时间t），就对比最先入队的元素，判断其是否出t-3000和t闭区间，是则不再题目的统计范围，移除。队列的长度，即为该区间里请求的次数。

class RecentCounter {

    LinkedList<Integer> queue;

    public RecentCounter() {
        queue = new LinkedList<>();
    }

    /**
     *
     * @param t 传入请求的时间
     * @return 返回[t-3000, 3000]闭区间的请求的数量，即队列长度
     */
    public int ping(int t) {
        queue.add(t);
        //peek拿到即将出队的元素（这就是来的最早的元素）
        //当传入的请求的时间减去3000大于将出队的元素时，移除即将出队的元素
        //如上面例子，3002进来时，3002 - 3000大于最开始的1，1出队，不再统计范围之内
        while(queue.size() > 0 && t - 3000 > queue.peek() ) {
            queue.pop();
        }
        return queue.size();
    }
}

测试：

public class P933 {
    public static void main(String[] args) {
        RecentCounter recentCounter = new RecentCounter();
        System.out.println(recentCounter.ping(1));      //1
        System.out.println(recentCounter.ping(100));    //2
        System.out.println(recentCounter.ping(3001));   //3
        System.out.println(recentCounter.ping(3002));   //3
        System.out.println(recentCounter.ping(3003));   //4
        System.out.println(recentCounter.ping(3200));   //4
    }
}