Monotonic queue: LC933 Number of Recent Calls

Problem

Number of Recent Calls

Explanation

The t is keeping on increasing, so we can use a monotonic queue to solve this problem in O(n)

Solution

class RecentCounter:
    def __init__(self):
        self.queue = collections.deque([])
    def ping(self, t: int) -> int:
        self.queue.append(t)
        while t - self.queue[0] > 3000:
            self.queue.popleft()
        return len(self.queue)

Thanks for reading.