python - 使用 itertools.accumulate 计算后缀最大值

Question

计算整数序列的后缀最大值的推荐方法是什么？

以下是基于问题定义的蛮力方法(O(n**2)时间):

>>> A
[9, 9, 4, 3, 6]
>>> [max(A[i:]) for i in range(len(A))]
[9, 9, 6, 6, 6]

一种使用itertools.accumulate() 的O(n) 方法如下，它使用两个列表构造函数:

>>> A
[9, 9, 4, 3, 6]
>>> list(reversed(list(itertools.accumulate(reversed(A), max))))
[9, 9, 6, 6, 6]

是否有更 pythonic 的方法来做到这一点？

Answer 1

切片反转使事情更简洁，嵌套更少:

list(itertools.accumulate(A[::-1], max))[::-1]

不过，它仍然是您想要捆绑到一个函数中的东西:

from itertools import accumulate

def suffix_maximums(l):
    return list(accumulate(l[::-1], max))[::-1]

如果您使用的是 NumPy，您需要 numpy.maximum.accumulate:

import numpy

def numpy_suffix_maximums(array):
    return numpy.maximum.accumulate(array[::-1])[::-1]