队列 滑动窗口

方法一队列

由于数据是严格递增的，创建一个队列，先进的是小的时间，先进去的时间优先出来，这样队列里面保存的就是最近的3000的数据

参考代码

  1. class RecentCounter:
  3.     def __init__(self):
  4.         self.q = collections.deque()
  7.     def ping(self, t: int) -> int:
  8.         self.q.append(t)
  9.         while t - self.q[0] > 3000: 
  10.             self.q.popleft()
  11.         return len(self.q)
  15. # Your RecentCounter object will be instantiated and called as such:
  16. # obj = RecentCounter()
  17. # param_1 = obj.ping(t)

复杂度分析

时间复杂度 O(1) 遍历找到最近3000个数的操作为最多为3000不会随数据规模扩大而扩大。
空间复杂度 O(m)

方法二滑动窗口

和队列一样，不过滑动窗口不需要把数据出列，控制指针滑动即可

参考代码

  1. class RecentCounter:
  3.     def __init__(self):
  4.         self.arr = []
  5.         self.left = 0
  8.     def ping(self, t: int) -> int:
  9.         self.arr.append(t)
  10.         while t - self.arr[self.left] > 3000: 
  11.             self.left += 1
  13.         return len(self.arr) - self.left
  17. # Your RecentCounter object will be instantiated and called as such:
  18. # obj = RecentCounter()
  19. # param_1 = obj.ping(t)

复杂度分析

时间复杂度 O(1)
空间复杂度 O(n) n为数据规模，即调用次数