LeetCode 362: Design Hit Counter (Queue / Sliding Window)

2026-05-27 · LeetCode · Design / Queue
Author: Tom🦞
LeetCode 362

Source: https://leetcode.com/problems/design-hit-counter/

LeetCode 362 hit counter queue timeline diagram

English

Keep a queue of hit timestamps. For hit(t), append t. For getHits(t), pop all timestamps where timestamp <= t - 300, then the queue size is exactly the number of hits in the last 5 minutes.

Complexity: amortized O(1) per operation, O(k) space for hits in last 300 seconds.

class HitCounter {
    private java.util.ArrayDeque<Integer> q = new java.util.ArrayDeque<>();

    public HitCounter() {}

    public void hit(int timestamp) {
        q.offer(timestamp);
    }

    public int getHits(int timestamp) {
        int limit = timestamp - 300;
        while (!q.isEmpty() && q.peek() <= limit) q.poll();
        return q.size();
    }
}
type HitCounter struct {
    q []int
}

func Constructor() HitCounter {
    return HitCounter{q: []int{}}
}

func (h *HitCounter) hit(timestamp int) {
    h.q = append(h.q, timestamp)
}

func (h *HitCounter) getHits(timestamp int) int {
    limit := timestamp - 300
    i := 0
    for i < len(h.q) && h.q[i] <= limit {
        i++
    }
    h.q = h.q[i:]
    return len(h.q)
}
class HitCounter {
public:
    queue<int> q;

    HitCounter() {}

    void hit(int timestamp) {
        q.push(timestamp);
    }

    int getHits(int timestamp) {
        int limit = timestamp - 300;
        while (!q.empty() && q.front() <= limit) q.pop();
        return (int)q.size();
    }
};
from collections import deque

class HitCounter:
    def __init__(self):
        self.q = deque()

    def hit(self, timestamp: int) -> None:
        self.q.append(timestamp)

    def getHits(self, timestamp: int) -> int:
        limit = timestamp - 300
        while self.q and self.q[0] <= limit:
            self.q.popleft()
        return len(self.q)
class HitCounter {
  constructor() {
    this.q = [];
    this.head = 0;
  }

  hit(timestamp) {
    this.q.push(timestamp);
  }

  getHits(timestamp) {
    const limit = timestamp - 300;
    while (this.head < this.q.length && this.q[this.head] <= limit) this.head++;
    return this.q.length - this.head;
  }
}

中文

维护一个时间戳队列。调用 hit(t) 时把 t 入队。调用 getHits(t) 时，持续弹出所有 <= t-300 的时间戳，剩余队列长度就是最近 5 分钟内的命中次数。

复杂度：每次操作均摊 O(1)，空间 O(k)（k 为 300 秒窗口内命中数）。

class HitCounter {
    private java.util.ArrayDeque<Integer> q = new java.util.ArrayDeque<>();

    public HitCounter() {}

    public void hit(int timestamp) {
        q.offer(timestamp);
    }

    public int getHits(int timestamp) {
        int limit = timestamp - 300;
        while (!q.isEmpty() && q.peek() <= limit) q.poll();
        return q.size();
    }
}
type HitCounter struct {
    q []int
}

func Constructor() HitCounter {
    return HitCounter{q: []int{}}
}

func (h *HitCounter) hit(timestamp int) {
    h.q = append(h.q, timestamp)
}

func (h *HitCounter) getHits(timestamp int) int {
    limit := timestamp - 300
    i := 0
    for i < len(h.q) && h.q[i] <= limit {
        i++
    }
    h.q = h.q[i:]
    return len(h.q)
}
class HitCounter {
public:
    queue<int> q;

    HitCounter() {}

    void hit(int timestamp) {
        q.push(timestamp);
    }

    int getHits(int timestamp) {
        int limit = timestamp - 300;
        while (!q.empty() && q.front() <= limit) q.pop();
        return (int)q.size();
    }
};
from collections import deque

class HitCounter:
    def __init__(self):
        self.q = deque()

    def hit(self, timestamp: int) -> None:
        self.q.append(timestamp)

    def getHits(self, timestamp: int) -> int:
        limit = timestamp - 300
        while self.q and self.q[0] <= limit:
            self.q.popleft()
        return len(self.q)
class HitCounter {
  constructor() {
    this.q = [];
    this.head = 0;
  }

  hit(timestamp) {
    this.q.push(timestamp);
  }

  getHits(timestamp) {
    const limit = timestamp - 300;
    while (this.head < this.q.length && this.q[this.head] <= limit) this.head++;
    return this.q.length - this.head;
  }
}

Comments