算法题最近的请求次数-智慧文博士

933. 最近的请求次数

问题描述

写一个RecentCounter类来计算最近的请求次数。

实现RecentCounter类：

RecentCounter()初始化计数器，请求数为0。
int ping(int t)在时间t添加一个新的请求（t表示以毫秒为单位的时间），并返回过去3000 毫秒内（包括t时刻）发生的请求数。

保证每次调用ping时，t的值都比之前的值大。

示例：

输入: ["RecentCounter","ping","ping","ping","ping"] [[],[1],[100],[3001],[3002]] 输出: [null,1,2,3,3] 解释: - ping(1) -> [1] -> 1个请求在[1-3000,1]范围内 - ping(100) -> [1,100] -> 2个请求在[100-3000,100]范围内 - ping(3001) -> [1,100,3001] -> 3个请求在[1,3001]范围内 - ping(3002) -> [1,100,3001,3002] -> 3个请求在[2,3002]范围内（1被排除）

算法思路

滑动窗口：

使用队列存储所有请求的时间戳
每次调用ping(t)时：
- 将当前时间t加入队列
- 移除队列中所有不在[t-3000, t]范围内的旧请求
- 返回队列的当前大小

代码实现

方法一：滑动窗口

importjava.util.Queue;importjava.util.LinkedList;classRecentCounter{privateQueue<Integer>requests;// 存储请求时间戳的队列privatestaticfinalintWINDOW_SIZE=3000;// 时间窗口大小/** * 构造函数：初始化RecentCounter */publicRecentCounter(){this.requests=newLinkedList<>();}/** * 在时间t添加请求，并返回过去3000毫秒内的请求数 * * @param t 请求时间戳（毫秒） * @return 过去3000毫秒内的请求数 */publicintping(intt){// 添加当前请求requests.offer(t);// 移除所有过期的请求（时间戳 < t - 3000）while(!requests.isEmpty()&&requests.peek()<t-WINDOW_SIZE){requests.poll();}// 返回当前窗口内的请求数returnrequests.size();}}

方法二：双端队列

importjava.util.Deque;importjava.util.ArrayDeque;classRecentCounter{privateDeque<Integer>requests;privatestaticfinalintWINDOW_SIZE=3000;publicRecentCounter(){this.requests=newArrayDeque<>();}publicintping(intt){requests.addLast(t);// 移除过期请求while(!requests.isEmpty()&&requests.getFirst()<t-WINDOW_SIZE){requests.removeFirst();}returnrequests.size();}}

算法分析

时间复杂度：
- 单次ping操作：均摊 O(1)
- 虽然有while循环，每个请求最多被加入和移除一次
空间复杂度：O(W)，W 是时间窗口内的最大请求数

算法过程

输入：[1,100,3001,3002]：

ping(1)：
- 队列：[1]
- 有效范围：[1-3000, 1] = [-2999, 1]
- 所有请求都有效，返回1
ping(100)：
- 队列：[1, 100]
- 有效范围：[100-3000, 100] = [-2900, 100]
- 所有请求都有效，返回2
ping(3001)：
- 队列：[1, 100, 3001]
- 有效范围：[3001-3000, 3001] = [1, 3001]
- 所有请求都有效（1 >= 1），返回3
ping(3002)：
- 队列：[1, 100, 3001, 3002]
- 有效范围：[3002-3000, 3002] = [2, 3002]
- 请求1过期（1 < 2），移除后队列：[100, 3001, 3002]
- 返回3

测试用例

publicstaticvoidmain(String[]args){// 测试用例1：标准示例RecentCounterrc1=newRecentCounter();System.out.println("Test 1:");System.out.println(rc1.ping(1));// 1System.out.println(rc1.ping(100));// 2System.out.println(rc1.ping(3001));// 3System.out.println(rc1.ping(3002));// 3// 测试用例2：密集请求RecentCounterrc2=newRecentCounter();System.out.println("\nTest 2:");for(inti=1;i<=5;i++){System.out.println(rc2.ping(i));// 1,2,3,4,5}// 测试用例3：稀疏请求（间隔很大）RecentCounterrc3=newRecentCounter();System.out.println("\nTest 3:");System.out.println(rc3.ping(1));// 1System.out.println(rc3.ping(4000));// 1 (1已过期)System.out.println(rc3.ping(8000));// 1 (4000已过期)// 测试用例4：边界情况RecentCounterrc4=newRecentCounter();System.out.println("\nTest 4:");System.out.println(rc4.ping(3000));// 1System.out.println(rc4.ping(6000));// 1 (3000刚好过期: 6000-3000=3000, 3000<3000)// 测试用例5：连续请求在边界RecentCounterrc5=newRecentCounter();System.out.println("\nTest 5:");System.out.println(rc5.ping(1));// 1System.out.println(rc5.ping(3001));// 2 (1仍在范围内: 3001-3000=1, 1>=1)System.out.println(rc5.ping(3002));// 2 (1过期: 3002-3000=2, 1<2)}