算法题 最近的请求次数

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被排除）

算法思路

滑动窗口：

1. 使用队列存储所有请求的时间戳
2. 每次调用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]：

1. ping(1)：

   • 队列：[1]
   • 有效范围：[1-3000, 1] = [-2999, 1]
   • 所有请求都有效，返回1

2. ping(100)：

   • 队列：[1, 100]
   • 有效范围：[100-3000, 100] = [-2900, 100]
   • 所有请求都有效，返回2

3. ping(3001)：

   • 队列：[1, 100, 3001]
   • 有效范围：[3001-3000, 3001] = [1, 3001]
   • 所有请求都有效（1 >= 1），返回3

4. 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)}

关键点

1. 滑动窗口：

   • 维护一个时间窗口[t-3000, t]
   • 动态添加新元素，移除过期元素
   • 队列大小就是窗口内的元素数量

2. 单调性：

   • 由于t严格递增，队列中的时间戳也是递增的
   • 过期元素总是集中在队列头部
   • 不需要检查队列中间或尾部的元素

常见问题

1. 为什么不用数组或列表？
   • 数组/列表删除头部元素需要O(n)时间
   • 队列的poll()操作是O(1)的