Leetcode - Design Hit Counter（2）

look_w

然后看答案看到了一种新的方法：

My code:

    public class HitCounter {
        Queue<Integer> q = new LinkedList<Integer>();
        /** Initialize your data structure here. */
        public HitCounter() {
            
        }
        
        /** Record a hit.
            @param timestamp - The current timestamp (in seconds granularity). */
        public void hit(int timestamp) {
            q.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 (!q.isEmpty() && timestamp - q.peek() >= 300) {
                q.poll();
            }
            
            return q.size();
        }
    }
     
    /**
     * Your HitCounter object will be instantiated and called as such:
     * HitCounter obj = new HitCounter();
     * obj.hit(timestamp);
     * int param_2 = obj.getHits(timestamp);
     */

reference:
https://discuss.leetcode.com/topic/48752/simple-java-solution-with-explanation/2

用一个queue来做。

然后这个方法其实存在一个问题。正如题目中说的，
当hit大量出现的时候，这个方法不能scale
加入 timestamp 1-3000 都 hit
那么， getHits(3001), 就需要先弹出几千个Integer，之后再返回。。。太慢了。
而我的 Treemap 做法，则是 log n 时间内就能算出来，可以scale