LeetCode LCR 042. 最近的请求次数
题目描述
题意分析
每次
ping(t)加入时刻t的一次请求，返回闭区间[t - 3000, t]内的请求数，包含本次请求和恰好位于左端点的请求。题目保证时间戳严格递增，可以按到达顺序维护有效请求。
解法：按时间过期的队列
核心思路
[!blue]
时间戳按从小到大到达，过期请求一定集中在队头。新请求从队尾加入后，不断删除小于
t - 3000的队头，直到最早请求仍在窗口内，此时后面的请求也全部有效。这个过程不会遗漏有效请求。此前被删除的时刻小于当时的窗口左端，而之后的左端只会继续增大，它们永远不会重新有效；此前未删除的请求和本次请求，则都在当前队列中等待检查。
清理结束后，队列恰好保存当前窗口内全部请求，长度就是答案。因为窗口包含左端点，淘汰条件必须使用严格小于。先加入当前请求再清理，也保证队列不会被删空：时刻
t本身一定有效。Java 使用双端队列完成尾部加入和头部删除，Go 通过追加切片、移动切片起点维护相同的逻辑队列，无需搬移剩余元素或重新遍历计数。
解题步骤
- 构造一个空队列。
- 每次调用先将
t加入队尾。- 只要队头小于
t - 3000，就继续移除队头，一次调用可能淘汰多条记录。- 队头合法后停止，返回队列长度。第一次调用时队列只含本次请求，返回 $1$。
代码实现
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();
}
}
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$ 的闭区间至多容纳 $3001$ 个请求。
关键点总结
[!green]
- 时间有序，使所有过期请求都位于队头，清理可以在首个有效请求处停止。
- 只淘汰严格早于左边界的记录，保留闭区间端点。
- 队列长度直接表示请求数量，复杂度按每条记录一进一出计算。
易错点总结
[!yellow]
- 用
<= t - 3000淘汰会错误删除左端点上的请求。- 只删除一次队头，可能留下其他过期记录；需要循环清理。
- 当前实现先入队再清理，保证至少保留本次请求。
- Go 更新持久队列的方法使用指针接收者，才能保留每次调用后的状态。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 346. 数据流中的移动平均值 | 简单 | 同样使用FIFO维护窗口，原题固定最近元素数，本题固定时间跨度，窗口大小会变化。 |
| 362. 敲击计数器 | 中等 | 同样统计时间窗口内请求，原题按秒允许同一时间多次命中，本题时间戳严格递增。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！