LeetCode 933. 最近的请求次数
题目描述
题意分析
每次调用
ping(t)都会新增一个发生在时间t的请求，并返回闭区间[t - 3000, t]内的请求数量，包括本次新请求和恰好位于左边界的历史请求。题目保证每次传入的整数时间严格递增。因此这是按时间统计最近三千毫秒，而不是只保存最近固定几次请求；已经比窗口左边界更早的请求，也不可能被未来查询重新计入。
解法：单调时间队列
核心思路
[!blue]
每次返回之前，队列恰好保存当前时间窗口内的全部请求。因为输入时间递增，新请求一定比已有请求更晚，直接追加到队尾，队列就自然按时间从早到晚排列，无需再排序。
当前窗口的左边界是
t - 3000。只要队首小于这个值，它就已经过期，应从队首删除；未来时间只会更大，左边界也只会向右移，所以这种删除是永久安全的，不需要保存完整历史。当队首不再过期时，由于后面的时间更晚，它们也都不小于左边界；同时没有历史请求超过当前
t，所以剩余队列恰好位于目标闭区间内，长度就是答案。代码先加入当前请求，再清理过期队首。新加入的
t自身一定合法，不会被这轮清理删掉，因此清理循环检查队首时始终至少还剩本次请求。某一次可能清理很多历史项，但每项总共只入队、出队各一次。
解题步骤
- 构造时准备一个空队列，保存尚未过期的请求时间。
ping(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)
}
复杂度分析
- 时间复杂度：一次调用若移除
k项，需 $O(k + 1)$；每个请求累计只进出一次，因此连续q次调用总计 $O(q)$，单次均摊 $O(1)$。- 空间复杂度：$O(W)$，
W为执行期间窗口内请求数的最大值。时间是严格递增的整数，固定闭区间最多容纳三千零一个不同时间戳，存储不随完整历史无限增长。
关键点总结
[!green]
- 输入时间递增，同时保证入队顺序和过期顺序都是单向的。
- 队首仍合法时，后面更晚的请求也合法，所以不必继续扫描。
- 闭区间的左端必须保留，清理条件使用严格小于。
- 先加入当前请求，既把它计入答案，也保证清理过程中队列不会为空。
易错点总结
[!yellow]
- 用小于等于左边界清理，会误删恰好相隔三千毫秒的合法请求。
- 一次只删除一个过期项，可能让更早的其他历史请求继续混在答案里。
- 没有把本次请求加入统计，返回值会少一次。
- 每次重新扫描全部历史，会重复检查再也不会有效的旧请求，放弃线性总开销的性质。
- 将这个队列规则直接用于乱序时间戳，无法保证所有过期请求都集中在队首。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 362. 敲击计数器 | 中等 | 同样对时间范围内的事件计数，原题窗口为 300 秒且允许同一秒多次命中，需要明确计数单位。 |
| 1004. 最大连续1的个数 III | 中等 | 同样只推进窗口两端，本题按时间范围清理而非按窗口内零的数量收缩。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！