LeetCode 933. 最近的请求次数
目录
题目描述
题意分析
每次调用
ping(t)，都要返回闭区间[t - 3000, t]内的请求数。题目保证t严格递增，这个条件比“统计区间”本身更重要：新请求只会从右侧进入窗口，过期请求也只会从左侧离开，因此可以维护一个单调向前的队列。队列只保存当前仍可能被统计的时间戳。先把
t入队，再不断移除所有< t - 3000的队首；清理结束后，队列中的每个时间戳都在目标闭区间内，队列长度就是答案。左边界是闭的，所以时间戳恰好等于t - 3000时不能删除。这是一道数据流设计题，不应为每次查询重新扫描所有历史请求。面试时要主动指出：严格递增保证了队列有序，也保证每个请求最多入队、出队各一次。
解法：单调时间队列
核心思路
维护不变量：一次
ping返回前，队列恰好包含所有落在当前窗口[t - 3000, t]内的请求时间。新的
t一定比队列中所有元素大，所以直接追加到队尾不会破坏有序性。随后只需观察队首：如果队首已经小于左边界，它是当前及以后所有窗口中最早过期的元素，可以永久删除；若队首仍合法，由于队列有序，后面的元素也一定合法，清理立即结束。例如依次调用
ping(1)、ping(100)、ping(3001)、ping(3002)：前三次队列分别为[1]、[1,100]、[1,100,3001]；处理3002时左边界为 2，先弹出 1，保留[100,3001,3002]，返回 3。这个过程也说明了为什么比较条件必须是< t - 3000而不是<=。
解题步骤
- 构造对象时创建一个空双端队列，用来保存尚未过期的时间戳。
- 每次
ping(t)先把t加到队尾，确保当前请求被计入。- 当队首
< t - 3000时持续弹出队首；等于左边界的请求仍合法，必须保留。- 清理完成后返回队列长度。
代码实现
class RecentCounter {
private final Deque<Integer> queue = new ArrayDeque<>();
public RecentCounter() {
}
public int ping(int t) {
queue.offerLast(t);
while (queue.peekFirst() < t - 3000) {
queue.pollFirst();
}
return queue.size();
}
}
type RecentCounter struct {
q []int
}
func Constructor() RecentCounter {
return RecentCounter{[]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:]
}
return len(this.q)
}
复杂度分析
- 时间复杂度：单次调用最坏为 $O(k)$，其中 $k$ 是本次被清理的过期请求数；均摊为 $O(1)$，因为每个时间戳只会入队一次、出队一次。连续调用 $n$ 次的总时间为 $O(n)$。
- 空间复杂度：$O(w)$，
w为任一时刻 3000 毫秒窗口内的请求数；最坏情况下为 $O(n)$。
关键点总结
- 严格递增的输入把问题变成了只从两端更新的滑动窗口，队列无需排序。
- 队列保存的是“仍在窗口内的全部请求”，而不是固定长度的最近若干次请求。
- 每次先入队再清理，当前请求一定属于
[t - 3000, t]，不会被误删。- 用“每个元素最多进出各一次”解释均摊复杂度，比只写结论更适合面试场景。
易错点总结
- 把闭区间写成开区间：若用
<= t - 3000清理，ping(1)后再ping(3001)会错误删除时间戳 1；两次请求都应被统计。- 先清理、后入队却忘记计入当前请求：当前
t永远合法，最稳妥的顺序是先追加再返回长度。- 每次遍历完整历史：功能正确但 $n$ 次调用会退化为 $O(n^2)$；过期数据应永久丢弃。
- 忽略
t严格递增的前提：队列方案依赖这个保证；若时间戳乱序，就不能只看队首决定哪些元素过期。
相似题目
| 题目 | 难度 | 与本题的联系 |
|---|---|---|
| LCR 042. 最近的请求次数 | 简单 | 同题变体，可直接复用“单调时间队列 + 清理过期队首”的不变量 |
| 346. 数据流中的移动平均值 | 简单 | 同样维护数据流窗口，但窗口按元素个数而不是时间范围划分 |