如何提高Python代码的时间复杂度？

Question

我的代码的目标是通过将每个数字添加到下一个更大的数字来对数字进行编码，如果没有找到更大的数字，我将使用相同的数字。 [4,3,7,3,2,8,6,1,10,3] =>[11,10,15,11,10,18,16,11,10,3]

我的代码的时间复杂度是 O(n²) 我想我可以做到 O(n log n) 我不知道我应该使用什么样的算法，因为我也想找到第一个更大的元素

我确实尝试过二分搜索，但我意识到它是从中间开始而不是第一个。

import queue 
q= queue.Queue()
a=[4,3,7,3,2,8,6,1,10,3]
for i in a:
    q.put(i)
encoded=[]
while q:
    current=q.get()
    for i in range(q.qsize()):
        if current<q.queue[i]:
            encoded.append(q.queue[i]+current)
            break

print(encoded)

Answer 1

Queue

不是必需的，只需迭代列表中的项目并找到局部最大值即可：

l = [4, 3, 7, 3, 2, 8, 6, 1, 10, 3]

out, last_processed, curr_max = [], 0, l[0]
for i, val in enumerate(l):
    if curr_max >= val:
        continue
    out.extend(l[j] + val for j in range(last_processed, i))
    last_processed, curr_max = i, val
out.extend(l[last_processed : i + 1])

print(out)

打印：

[11, 10, 15, 11, 10, 18, 16, 11, 10, 3]