队列题目：最近的请求次数

题目

标题和出处

标题：最近的请求次数

出处：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$ 是严格单调递增的，因此按照调用顺序存储请求时间可以得到请求时间的严格递增序列。每次调用 $\text{ping}$ 方法要求返回过去 $3000$ 毫秒内发生的所有请求数，因此可以将请求时间序列中的距离请求时间超过 $3000$ 毫秒的请求删除，然后计算请求时间序列中的请求数，即为过去 $3000$ 毫秒内发生的所有请求数。

由于最早发生的请求会最先被删除，因此请求时间序列满足先进先出的特点，可以使用队列实现请求时间序列，在构造方法中初始化队列。

对于 $\text{ping}$ 方法，首先将过时的请求出队列，如果队列不为空且队首元素距离当前请求时间超过 $3000$ 毫秒，则将队首元素出队列，重复该操作直到队列变为空或者队首元素距离当前请求时间不超过 $3000$ 毫秒。然后将当前请求时间入队列，此时队列内的元素个数即为过去 $3000$ 毫秒内发生的所有请求数，返回队列内的元素个数即可。

代码

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)$。每个元素最多入队和出队各一次，因此方法 $\text{ping}$ 的均摊时间复杂度是 $O(1)$。

• 空间复杂度：$O(n)$，其中 $n$ 是请求次数。空间复杂度主要取决于队列空间，队列内存储最近 $3000$ 毫秒的请求，空间复杂度是 $O(n)$。