Python FInd过去k项中的最大数字

Question

给定一个整数数组和一个整数值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)

Answer 1

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

1. 让我们保持对的双端队列(值,位置).最初,它是空的.

2. 当新元素到达时,请执行以下操作:当前元素的位置超出范围(小于i-K)时,弹出它.虽然后面元素的值小于新元素,但弹出它.最后,将一对(当前元素,其位置)推到双端队列的后面.

3. 当前位置的答案是双端队列的前部元素.

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