LeetCode算法题(Go语言实现)_27

题目

写一个 RecentCounter 类来计算特定时间范围内最近的请求。
请你实现 RecentCounter 类：
RecentCounter() 初始化计数器，请求数为 0 。
int ping(int t) 在时间 t 添加一个新请求，其中 t 表示以毫秒为单位的某个时间，并返回过去 3000 毫秒内发生的所有请求数（包括新请求）。确切地说，返回在 [t-3000, t] 内发生的请求数。
保证 每次对 ping 的调用都使用比之前更大的 t 值。

一、代码实现

type RecentCounter struct {queue []int
}func Constructor() RecentCounter {return RecentCounter{queue: make([]int, 0)}
}func (rc *RecentCounter) Ping(t int) int {rc.queue = append(rc.queue, t)// 移除窗口外的请求（t-3000是闭区间起点）for len(rc.queue) > 0 && rc.queue[0] < t-3000 {rc.queue = rc.queue[1:]}return len(rc.queue)
}

二、算法分析

1. 核心思路

   • 队列维护窗口：利用队列先进先出特性存储请求时间序列
   • 滑动窗口机制：每次新请求触发窗口左边界更新，移除过期请求
   • 严格递增特性：题目保证输入严格递增，无需排序操作

2. 关键步骤

   • 入队操作：将新请求时间t添加到队列尾部
   • 窗口校准：循环检查队首元素，移除所有< t-3000的过期请求
   • 实时统计：队列剩余元素数量即为窗口内请求总数

3. 复杂度

   指标	值	说明
   时间复杂度	均摊 O(1)	每个元素最多入队、出队各一次
   空间复杂度	O(n)	存储最多 n 个请求时间戳

三、图解示例

四、边界条件与扩展

1. 特殊场景处理

   • 最小时间窗口：当t=3000时，窗口变为[0,3000]
   • 连续过期请求：如输入[1,2,3,4000]，前三次请求均过期
   • 大时间跨度：t=10^9时需保证数值运算不溢出

2. 多语言实现

# Python实现（collections.deque优化）
from collections import deque
class RecentCounter:def __init__(self):self.q = deque()def ping(self, t: int) -> int:self.q.append(t)while self.q < t - 3000:self.q.popleft()return len(self.q)

// Java实现（LinkedList优化）
class RecentCounter {private LinkedList<Integer> queue;public RecentCounter() {queue = new LinkedList<>();}public int ping(int t) {queue.offer(t);while (queue.peek() < t - 3000) {queue.poll();}return queue.size();}
}

3. 算法对比

方法	时间复杂度	空间复杂度	优势
队列法	均摊 O(1)	O(n)	最优时间复杂度
二分查找法	O(logn)	O(n)	适合频繁查询历史数据
暴力遍历法	O(n)	O(1)	仅适用于极低频请求

五、总结与扩展

1. 数学本质

   • 滑动窗口公式：维护满足 t_i ∈ [t-3000, t] 的连续时间序列
   • 单调性保证：严格递增特性使队列保持有序，避免重复扫描

2. 工程优化

   • 内存预分配：根据最大调用次数 10^4 预分配队列容量
   • 数据结构选择：双端队列比普通队列更高效（如Java的ArrayDeque）

3. 扩展应用

   • 实时监控系统：统计最近N秒的请求频率
   • 股票交易系统：计算移动时间窗口内的交易量
   • 物联网设备：监测传感器数据的实时波动范围