python - 为什么队列是查找最近调用数量的最佳方法？ 【Leetcode问题】

Question

我刚刚在 Leetcode 上解决了“最近通话次数”问题。我读到它希望我返回 ping 数量，但不知道如何去做。

说明在这里:

Write a class RecentCounter to count recent requests.

It has only one method: ping(int t), where t represents some time in milliseconds.

Return the number of pings that have been made from 3000 milliseconds ago until now.

Any ping with time in [t - 3000, t] will count, including the current ping.

It is guaranteed that every call to ping uses a strictly larger value of t than before.

我了解到您必须立即知道您需要使用队列。我不知道，只是想知道是否有人可以解释为什么需要使用队列来解决这个问题。这是一种解决方案。

import collections

class recentCounter:
    def __init__(self):
        self.p = collections.deque()

    def ping(self, t: int):
        self.p.append(t)
        while self.p[0] < t - 3000:
            self.p.popleft()
        return len(self.p)

Answer 1

队列只是数组的子类，其中新值追加到底部，旧值从顶部popleft添加。

您并不绝对需要这个来解决您的问题；您可以将每个新值附加到带有时间戳的数组中，然后迭代该数组以仅返回最后三秒的值。然而，队列要优雅得多。此解决方案仅在必要时保留数组，然后不需要额外的工作即可产生所需的结果。