队列｜ Leetcode 362

Leetcode 分类刷题 —— 队列（Queue）

1、题目描述:

Leetcode 362. Design Hit Counter 敲击计数器

Design a hit counter which counts the number of hits received in the past 5 minutes.
Each function accepts a timestamp parameter (in seconds granularity) and you may assume that calls are being made to the system in chronological order (ie, the timestamp is monotonically increasing). You may assume that the earliest timestamp starts at 1.

设计一个敲击计数器，使它可以统计在过去5分钟内被敲击次数。
每个函数会接收一个时间戳参数（以秒为单位），你可以假设最早的时间戳从1开始，且都是按照时间顺序对系统进行调用（即时间戳是单调递增）。
在同一时刻有可能会有多次敲击。

2、解题思路：

使用一个队列来记录时间戳，每次点击时将当前时间戳加入队列。
在查询过去5分钟内的点击量时，我们遍历队列中的元素，将时间戳在过去5分钟之前的元素出队（删除过期元素）。
最后，返回队列中元素的数量即为过去5分钟内的点击量。

3、代码

import java.util.*;

class HitCounter {

    private Queue<Integer> queue;

    /** Initialize your data structure here. */
    public HitCounter() {
        queue = new LinkedList<>();
    }

    /** Record a hit.
     @param timestamp - The current timestamp (in seconds granularity). */
    public void hit(int timestamp) {
        queue.offer(timestamp);
    }

    /** Return the number of hits in the past 5 minutes.
     @param timestamp - The current timestamp (in seconds granularity). */
    public int getHits(int timestamp) {
        while (!queue.isEmpty() && queue.peek() <= timestamp - 300) {
            queue.poll();
        }
        return queue.size();
    }
}