难度: Medium
Submission
运行时间: 27 ms
内存: 0.0 MB
class HitCounter:
def __init__(self):
"""
Initialize your data structure here.
"""
self.counter = collections.deque()
def hit(self, timestamp: int) -> None:
"""
Record a hit.
@param timestamp - The current timestamp (in seconds granularity).
"""
self.counter.append(timestamp)
def getHits(self, timestamp: int) -> int:
"""
Return the number of hits in the past 5 minutes.
@param timestamp - The current timestamp (in seconds granularity).
"""
while self.counter and timestamp - self.counter[0] >= 300:
self.counter.popleft()
return len(self.counter)
# Your HitCounter object will be instantiated and called as such:
# obj = HitCounter()
# obj.hit(timestamp)
# param_2 = obj.getHits(timestamp)
Explain
该题解的整体思路是利用一个双向队列 (deque) 存储每次敲击的时间戳。当调用 hit 方法时，时间戳被添加到 deque 的尾部。当调用 getHits 方法时，该方法首先移除 deque 中所有超过 5 分钟之前的时间戳，然后返回 deque 中剩余的时间戳数量，即为最近 5 分钟内的敲击次数。
时间复杂度: O(1)
空间复杂度: O(300) 或 O(1)，视时间窗口大小为固定值时可认为是常数空间。
import collections
class HitCounter:
def __init__(self):
\"\"\"
初始化数据结构。
使用 collections.deque 来高效地进行队首和队尾操作。
\"\"\"
self.counter = collections.deque()
def hit(self, timestamp: int) -> None:
\"\"\"
记录一个敲击。
将时间戳添加到双端队列尾部。
@param timestamp - 当前时间戳（秒）。
\"\"\"
self.counter.append(timestamp)
def getHits(self, timestamp: int) -> int:
\"\"\"
返回过去 5 分钟内的敲击次数。
移除所有超过 5 分钟的时间戳，然后返回队列长度。
@param timestamp - 当前时间戳（秒）。
\"\"\"
while self.counter and timestamp - self.counter[0] >= 300:
self.counter.popleft()
return len(self.counter)
Explore
双向队列（deque）被选择用于存储时间戳主要是因为其在前端和后端操作的高效性。在这个问题中，我们需要频繁地在队列的尾部添加新的时间戳（hit操作），同时也需要从队列的头部移除过期的时间戳（getHits操作）。使用列表（如Python中的list）进行这样的操作会非常低效，因为列表的头部插入或删除操作需要O(n)时间复杂度，其中n是列表的长度。而链表虽然可以在O(1)时间复杂度内完成这些操作，但其在实际的内存结构中不如deque连续，可能导致更高的缓存未命中率和额外的内存开销。双向队列结构可以在两端进行O(1)时间复杂度的插入和删除操作，非常适合本问题的需求。
如果在`getHits`方法调用时，双向队列内的所有时间戳都还在5分钟以内，则不会执行任何的移除操作，此时该方法主要执行的是返回队列长度的操作，这是一个O(1)时间复杂度的操作。因此，在所有时间戳都在5分钟以内的情况下，`getHits`方法的时间复杂度为O(1)。
当`hit`方法在短时间内被频繁调用时，每次调用都会向双向队列的尾部添加一个新的时间戳，导致队列的长度增加。如果这些`hit`操作发生在极短的时间间隔内，队列的长度可能会迅速增长，从而占用更多的内存资源。尤其是在高流量的应用场景下，队列可能会暂时存储大量的时间戳，直到这些时间戳超过5分钟后才开始逐渐被移除。这种情况下，内存的使用会随着队列长度的增加而增加，可能导致内存压力或在极端情况下导致内存溢出，特别是当系统内存有限时更需注意这一点。因此，正确管理和监控内存使用，以及合理设定时间戳的存储策略，对于维持系统稳定性和性能是非常关键的。