Queue Topic: Recent Requests

题目

标题和出处

标题：最近的请求次数

出处：933. 最近的请求次数

难度

3 级

题目描述

要求

写一个 $\text{RecentCounter}$ 类来计算特定时间范围内最近的请求.

请你实现 $\text{RecentCounter}$ 类：

• $\text{RecentCounter()}$ 初始化计数器,请求数为 $\text{0}$.
• $\text{int ping(int t)}$ 在时间 $\text{t}$ 添加一个新请求,其中 $\text{t}$ 表示以毫秒为单位的某个时间,并返回过去 $\text{3000}$ 毫秒内发生的所有请求数（包括新请求）.确切地说,返回在 $\text{[t - 3000, t]}$ 内发生的请求数.

保证每次对 $\text{ping}$ 的调用都使用比之前更大的 $\text{t}$ 值.

示例

示例 1：

输入：
$\text{["RecentCounter", "ping", "ping", "ping", "ping"]}$
$\text{[[], [1], [100], [3001], [3002]]}$
输出：
$\text{[null, 1, 2, 3, 3]}$
解释：
$\text{RecentCounter recentCounter = new RecentCounter();}$
$\text{recentCounter.ping(1);}$ // $\text{requests = [1]}$,范围是 $\text{[-2999, 1]}$,返回 $\text{1}$
$\text{recentCounter.ping(100);}$ // $\text{requests = [1, 100]}$,范围是 $\text{[-2900, 100]}$,返回 $\text{2}$
$\text{recentCounter.ping(3001);}$ // $\text{requests = [1, 100, 3001]}$,范围是 $\text{[1, 3001]}$,返回 $\text{3}$
$\text{recentCounter.ping(3002);}$ // $\text{requests = [1, 100, 3001, 3002]}$,范围是 $\text{[2, 3002]}$,返回 $\text{3}$

数据范围

• $\text{1}\le \text{t}\le {\text{10}}^{\text{9}}$
• 保证每次对 $\text{ping}$ 调用所使用的 $\text{t}$ 值都严格递增
• 至多调用 $\text{ping}$ 方法 ${\text{10}}^{\text{4}}$ 次

解法

思路和算法

由于每次调用 $\text{ping}$ 方法时,请求时间 $t$ 是严格单调递增的,Therefore, storing request times in the order of invocation results in a strictly increasing sequence of request times.每次调用 $\text{ping}$ The method asks to go back to the past $3000$ 毫秒内发生的所有请求数,So the distance request time in the request time series can be exceeded $3000$ milliseconds for request deletion,Then count the number of requests in the request time series,the past $3000$ 毫秒内发生的所有请求数.

Because the oldest request will be deleted first,Therefore, the request time series meets the characteristics of first-in, first-out,Request time series can be implemented using queues,在构造方法中初始化队列.

对于 $\text{ping}$ 方法,Dequeue stale requests first,If the queue is not empty and the head of the queue is more than the current request time $3000$ 毫秒,则将队首元素出队列,This operation is repeated until the queue becomes empty or the head of the queue is within the current request time $3000$ 毫秒.然后将当前请求时间入队列,At this time, the number of elements in the queue is the past $3000$ 毫秒内发生的所有请求数,Return the number of elements in the queue.

代码

class RecentCounter {
    
    static final int RANGE = 3000;
    Queue<Integer> queue;

    public RecentCounter() {
    
        queue = new ArrayDeque<Integer>();
    }
    
    public int ping(int t) {
    
        while (!queue.isEmpty() && queue.peek() < t - RANGE) {
    
            queue.poll();
        }
        queue.offer(t);
        return queue.size();
    }
}

复杂度分析

• 时间复杂度：构造方法的时间复杂度是 $O(1)$,方法 $\text{ping}$ 的均摊时间复杂度是 $O(1)$.Each element is enqueued and dequeued at most once,因此方法 $\text{ping}$ 的均摊时间复杂度是 $O(1)$.

• 空间复杂度：$O(n)$,其中 $n$ is the number of requests.The space complexity mainly depends on the queue space,The most recent is stored in the queue $3000$ 毫秒的请求,空间复杂度是 $O(n)$.