Python在过去的k个项目中找到最大的数字

给定一个整数数组和一个整数值 K，我的任务是编写一个函数，该函数将数组中该值的最高数字以及之前的 K 个条目打印到标准输出。

示例输入:

tps: 6, 9, 4, 7, 4, 1
k: 3

示例输出:

6
9
9
9
7
7

有人告诉我，我编写的代码对于大型数据集可以更加高效。我怎样才能使这段代码最有效？

def tweets_per_second(tps, k):
    past = [tps[0]]
    for t in tps[1:]:
        past.append(t)
        if len(past) > k: past = past[-k:]
        print max(past)

最佳答案

您可以使用单调队列(对于任何 k 值，O(n))来实现线性时间复杂度。想法如下:

让我们维护一个双端队列(值，位置)。最初，它是空的。

当新元素到达时，执行以下操作:当前面元素的位置超出范围(小于 i - K)时，弹出它。当 back 元素的值小于新元素时，弹出它。最后，将一对(当前元素，它的位置)推到双端队列的后面。

当前位置的答案是双端队列的前元素。

每个元素只添加到双端队列一次，最多删除一次。因此，时间复杂度是线性的，它不依赖于 K。这个解决方案是最优的，因为仅仅读取输入是 O(n)。

关于Python在过去的k个项目中找到最大的数字，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/27870329/