巧用队列轻松解决3000ms时间窗口请求计数问题 : Leetcode 933

在算法刷题与实际开发中，时间窗口内的统计问题是高频考点，而队列作为一种先进先出（FIFO）的数据结构，恰好是解决这类问题的“利器”。今天就和大家分享一道经典的时间窗口请求计数题，这道题堪称队列的“裸题”，掌握其解题思路，能轻松应对同类的时间窗口统计场景，话不多说，咱们直接开讲～

一、题目核心需求剖析

这道题的核心要求十分清晰：实现一个方法，每次传入一个请求的时间戳，程序需要实时返回当前时间戳距离3000毫秒（3秒）内的请求总次数。

为了让大家更直观理解，举两个典型的例子：

1. 若请求依次出现在1000ms、100000ms、3001000ms这三个时间点，当处理3001000ms的请求时，该时间戳与前两个请求的时间差均未超过3000ms，因此返回请求次数为3；

2. 当请求出现在3002000ms时，其与1000ms请求的时间差为3001000ms，超出了3000ms的范围，因此该请求需排除，最终返回请求次数为2。

简单来说，我们需要维护一个3000ms的滑动时间窗口，窗口内始终保留符合时间要求的请求时间戳，窗口的大小就是最终要返回的请求次数。

二、解题思路：队列的天然适配性

为什么说这道题是队列的“裸题”？因为队列先进先出的特性，与滑动时间窗口的“剔除过期元素、加入新元素”逻辑高度契合，核心解题思路可以总结为三步法，简单到两分钟就能吃透：

1. 新元素入队：每次接收到新的请求时间戳，将其直接加入队列尾部；

2. 剔除过期元素：以当前新时间戳为基准，检查队列头部的元素（最早的请求时间戳），若两者的时间差大于3000ms，则将队首元素出队，重复此操作直到队首元素为有效时间戳；

3. 返回队列长度：经过过期元素剔除后，队列中剩余的所有元素都是3000ms时间窗口内的有效请求，此时队列的长度就是当前的有效请求次数。

整个过程无需复杂的遍历与计算，队列的操作让滑动窗口的维护变得极其简洁，时间复杂度上，每个元素最多入队一次、出队一次，整体均摊时间复杂度为O(1)，性能拉满～

队列操作流程可视化

为了更清晰展示整个过程，我们用Mermaid绘制队列的核心操作流程图，直观感受每一步的执行逻辑：

图表说明：该流程图展示了单次请求处理的完整逻辑，其中“判断t - 队首元素 > 3000ms”为循环判断，直到队首元素满足时间要求为止，确保队列内无过期的请求时间戳。

三、代码实现：C++队列的极简应用

在C++中，STL库为我们提供了现成的queue容器，其封装了push()（入队）、pop()（出队）、front()（获取队首元素）、size()（获取队列长度）等核心方法，完全匹配我们的解题需求，无需手动实现队列，直接调用即可。

核心代码片段

#include <queue> using namespace std; queue<int> q; // 定义全局队列，存储请求的时间戳 // 处理请求的核心方法，t为当前请求的时间戳 int ping(int t) { q.push(t); // 新时间戳入队 // 循环剔除过期的队首元素 while (t - q.front() > 3000) { q.pop(); } return q.size(); // 返回有效请求数 }

代码关键说明

1. 队列定义：将队列定义为全局变量，保证多次ping方法调用时，队列的状态能持续维护，记录所有历史有效请求；

2. 入队操作：q.push(t)将新请求的时间戳直接加入队列尾部，时间复杂度O(1)；

3. 过期判断：通过while循环持续检查队首元素，若t - q.front() > 3000，说明队首元素已超出3000ms时间窗口，执行q.pop()出队，直到队首元素有效；

4. 返回结果：q.size()直接返回队列当前的元素个数，也就是3000ms内的有效请求次数，这一步也是本题的最终答案。

代码执行效果验证

我们用题目中的典型案例测试代码，执行过程与结果如下表所示：

四、场景延伸：队列的滑动窗口应用拓展

这道题虽然简单，但它的解题思路可以迁移到众多实际开发与算法刷题的场景中，比如：

1. 接口限流：实际项目中，接口的“每秒请求数（QPS）限制”，本质就是1秒时间窗口内的请求计数，可直接复用该队列思路；

2. 滑动窗口求和/统计：如求一个数组中，长度为k的滑动窗口内的元素和、最大值/最小值，队列（或单调队列）都是核心解法；

3. 日志实时统计：统计某段时间内的系统日志打印次数、错误请求次数等，时间窗口的维护均可借鉴此思路。

可以说，掌握了“队列维护滑动时间窗口”的核心逻辑，就掌握了一类题的解题钥匙，这也是这道“简单题”的价值所在——夯实基础，以小见大。

五、总结

这道3000ms时间窗口请求计数题，看似是一道算法题，实则是对队列数据结构核心特性的考察。解题的关键不在于复杂的代码编写，而在于思路的选择——发现队列与滑动时间窗口的适配性，就能化繁为简，用几行代码轻松解决问题。

在算法学习中，很多时候不是“会不会写代码”，而是“会不会选数据结构”。合适的数据结构，能让问题的解决效率呈指数级提升，而队列作为基础数据结构，其在滑动窗口、任务排队、广度优先搜索（BFS）等场景中的应用，值得我们反复琢磨、熟练掌握。

后续我们还会分享更多算法刷题中的智力发散题与经典题型，从基础到进阶，一步步吃透算法核心逻辑，敬请期待～