LeetCode LCR 042. 最近的请求次数
目录
题目描述
题意分析
题目目标：设计一个计数器，每次
ping(t)表示在毫秒时刻t发生了一次请求，返回值是发生在时间区间[t - 3000, t]内的请求总数（含两端）。
核心约束：题目保证每次传入的t严格大于上一次，这是最关键的信号——请求天然按时间有序到达，不需要任何排序或查找，只要从最早的一端逐个淘汰过期记录即可。
边界处理：区间左端闭合，恰好等于t - 3000的请求必须计入；本次请求自身也在区间内，答案至少为 1；t可能小于 3000，此时t - 3000为负数，所有历史请求都还有效。
实现取舍：过期的请求一旦被淘汰，就永远不可能因为后续更大的t而重新变得有效，所以淘汰是不可逆的，可以放心地物理删除而不必打标记。
解法：LCR处理
核心思路
最朴素的做法是把所有时刻存进一个数组，每次
ping从头到尾扫一遍统计落在[t - 3000, t]内的个数。这样单次是 $O(n)$，n次调用总代价 $O(n^2)$；即便借助有序性改成二分找左端点，也仍要保留全部历史，内存没有上限。
瓶颈在于每次都重新审视那些早已过期的记录。观察到两点：其一，右端点随调用单调右移，因此左边界t - 3000也单调右移；其二，先到达的请求一定先过期。两个"先进先出"叠在一起，说明有效记录构成的是一个只在尾部进入、只在头部离开的连续区间。
由此确定不变量：任意一次ping返回之前，容器里从头到尾保存的恰好是当前仍然有效（时刻不小于t - 3000）的全部请求时刻，且严格升序排列。既然容器里的元素全部有效且不重不漏，答案就直接是容器长度，连遍历统计都可以省掉。
维护这条不变量只需两步：先把新时刻t追加到尾部（它一定是最大的，升序性得以保持），再从头部不断弹出小于t - 3000的时刻。头部是最小值，一旦头部合法就说明后面全部合法，可以立刻停止。
解题步骤
- 准备一个双端容器
q作为唯一状态。为什么选双端结构：新请求只从尾部进入、过期请求只从头部离开，两端操作都必须是 $O(1)$，若用普通数组从头删除，每次都要整体搬移元素。- 每次
ping(t)先执行q.offerLast(t)把当前时刻入队。为什么先入队再清理：t本身一定落在[t - 3000, t]内，先入队既保证接下来的清理循环里容器非空、不必额外判空，也让"长度即答案"这条不变量在返回时立刻成立。- 用
while (q.peekFirst() < t - 3000) q.pollFirst()清除过期记录。为什么用严格小于而不是小于等于：区间左端是闭的，时刻恰好等于t - 3000的请求仍然有效，写成<=会把它误删，答案少 1。- 为什么循环可以在头部合法时立即停止：容器内时刻严格升序，头部是最小值，它都不过期，后面的更不可能过期，因此不存在"漏掉某个过期元素"的风险。
- 返回
q.size()。为什么不需要再遍历计数：不变量保证容器里的每个元素都是有效请求，且有效请求都在容器里，长度就是答案。- 以
具体用例：依次调用ping(1)、ping(100)、ping(3001)、ping(3002)走一遍。第一次入队后q = [1]，左边界为-2999，头部 1 不小于它，不弹出，返回 1。第二次入队后q = [1, 100]，左边界为-2900，头部仍合法，返回 2。第三次入队后q = [1, 100, 3001]，左边界为3001 - 3000 = 1，头部是 1，判定1 < 1为假恰好保留，这正是闭区间左端的体现，返回 3。第四次入队后q = [1, 100, 3001, 3002]，左边界为 2，头部 1 满足1 < 2被弹出，新头部 100 判定100 < 2为假，循环停止，容器变成[100, 3001, 3002]，返回 3。
代码实现
// 核心实现：LCR处理，维护必要状态并避免重复处理。
class RecentCounter {
private Deque<Integer> q;
public RecentCounter() {
q = new LinkedList<>();
}
public int ping(int t) {
q.offerLast(t);
while (q.peekFirst() < t - 3000) {
q.pollFirst();
}
return q.size();
}
}
// 核心实现：LCR处理，维护必要状态并避免重复处理。
type RecentCounter struct {
q []int
}
func Constructor() RecentCounter {
return RecentCounter{
q: []int{},
}
}
func (this *RecentCounter) Ping(t int) int {
this.q = append(this.q, t)
for this.q[0] < t-3000 {
this.q = this.q[1:len(this.q)]
}
return len(this.q)
}
复杂度分析
- 时间复杂度：
n次调用总计 $O(n)$，单次均摊 $O(1)$。凭什么：每个时刻最多入队一次、出队一次，清理循环的总迭代次数被出队总数卡死，不会因为某次调用弹出很多元素而让总量变大。- 空间复杂度：$O(w)$，其中
w是 3000 毫秒窗口内可能出现的最大请求数。凭什么：过期记录被物理删除，容器长度始终等于当前有效请求数，与总调用次数无关。
关键点总结
- 当查询区间的两个端点都随时间单调移动时，维护"当前有效元素恰好构成一段连续区间"这条不变量，就能把每次查询压成常数级，这是所有滑动区间计数题的共同骨架。
- 均摊分析是这类写法的关键论据：内层循环单次可能弹出很多元素，但每个元素一生只被弹出一次，总量仍是线性的，面试时要主动把这句话讲出来。
- 先入队再清理，可以让"容器非空"成为循环的天然前提，省掉判空分支；这种"先建立后修复"的顺序往往比"先修复后建立"少一堆边界。
- 区间开闭直接决定比较符号，把"闭区间左端用严格小于淘汰"当成固定对应关系记住，比每次临场推导更稳。
- 面试视角：题面里"
t严格递增"这句话是本解法的许可证，答题时应第一时间指出它，并顺势补充"如果时刻可以乱序到达，就得改用按时间有序的结构或转成离线处理"，展示对约束的敏感度。
易错点总结
- 错误写法：清理条件写成
while (q.peekFirst() <= t - 3000)→ 依次ping(1)、ping(3001)，第二次把时刻 1 弹出，返回 1 而不是正确的 2。- 错误写法：先清理再把
t入队 → 首次调用ping(1)时容器为空，peekFirst()返回null触发拆箱空指针异常，Go 里则是对空切片取q[0]直接越界 panic。- 错误写法：用
if代替while只弹出一个过期元素 → 依次ping(1)、ping(2)、ping(3002)，只有时刻 1 被弹出，时刻 2 残留，返回 3 而不是正确的 1。- 错误写法：把判定改写成
t - q.peekFirst() > 3000时顺手用了>=→ping(1)后再ping(3001)，差值恰为 3000 被判为过期，同样丢掉边界上的那次请求。- 错误写法：返回值改成遍历容器重新统计
count→ 结果虽仍正确，但单次退化为 $O(w)$，在 $10^4$ 次调用且窗口内请求密集时明显变慢，也说明没有意识到"容器内元素全部有效"这条不变量。- 错误写法：Go 中方法写成值接收者
func (this RecentCounter) Ping(t int) int→ 每次操作的是结构体副本，入队结果不会写回，第二次ping时容器仍为空，返回值永远是 1。- 错误写法：用一个整型变量记录上次计数再增量修正，只减 1 → 依次
ping(1)、ping(2)、ping(3003)，实际有两条同时过期却只减掉一条，返回 2 而不是 1。- 错误写法：把时刻存成
int之外的窄类型，或在自定义变种里用short承载毫秒时间戳 →t达到 $10^9$ 级别时直接溢出成负数，左边界比较全部失效。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| LCR 041. 数据流中的移动平均值 | 简单 | 窗口按元素个数而非时间界定，还要增量维护窗口和 |
| 362. 敲击计数器 | 中等 | 同一秒可能多次敲击，需要按秒分桶聚合而非逐条入队 |
| 901. 股票价格跨度 | 中等 | 淘汰依据从时间变成大小关系，需要单调栈而非先进先出 |
| 239. 滑动窗口最大值 | 困难 | 窗口内要的是极值，出队规则同时来自窗口和单调性 |
| 622. 设计循环队列 | 中等 | 关注队列本身的定长实现与队空队满的区分 |