力扣933题:队列的妙用:如何高效统计最近请求

文章封面

6

题目重解:

我们需要设计一个能统计最近3000毫秒内请求次数的系统。每当新的请求到来时,它会带有时间戳t,我们需要返回过去3000毫秒内(包括当前)发生的请求总数。这就像是在时间轴上维护一个滑动窗口,只关注最近3秒内的活动。

解题思路解析:

1.初始化:创建空队列存储时间戳

2.清理过期请求:每次新请求到来时,移除所有超过3000毫秒的旧请求

3.添加新请求:将当前请求时间戳加入队列

4.返回计数:队列长度即为有效请求数 整个过程确保了队列中只保留最近3000毫秒的请求,实现了O(1)均摊时间复杂度的操作。

代码注释版:

private: 
    queue count; // 存储请求时间戳的队列
public: 
    RecentCounter() {} // 构造函数初始化
    int ping(int t) {
       // 移除所有超过3000毫秒的旧请求
       while (!count.empty()) {
           int a = count.front(); // 检查队首元素
           if (a < t - 3000)
               count.pop(); // 移除过期请求
           else
               break; // 遇到第一个有效请求就停止
       }
       count.push(t); // 加入新请求
       return count.size(); // 返回有效请求数
    }
};

原文:https://www.xinaozhilu.cn/list/36.html

评论

暂无评论