如何高效地找到最小长度的峰值？

Question

我有一个整数列表/数组，如果它先增后减，就称为峰值子数组。例如：

[5,5,4,5,4]

包含

[4,5,4]

这是一个峰值。

还要考虑

[6,5,4,4,4,4,4,5,6,7,7,7,7,7,6]

包含哪些内容

[6,7,7,7,7,7,6]

问题

给定一个输入列表，我想找到其中包含的所有峰值，并报告它们的最小长度。在上面的示例中，[5,6,7,7,7,7,7,6] 也是一个峰值，但我们删除第一个元素后它仍然是峰值，因此我们不会报告它。

因此，对于输入列表：

<p>which is a peak.</p>

L = [5,5,5,5,4,5,4,5,6,7,8,8,8,8,8,9,9,8]

我们将返回

[4,5,4] and [8,9,9,8] only.

我在设计一个好的算法方面遇到了问题。非常感谢您提供任何帮助。

- Simd

---

@OlivierMelançon 是的 - Simd

那么像[4, 5, 5, 2]这样的东西怎么办？或者元素保证只会变化1。 - I Funball

@IFunball 那也是一个峰值。但是当它们只改变1时，你有更简单的方法吗？ - Simd

@OlivierMelançon 谢谢您的回复。我还在努力理解它以及它的速度会有多快。这很复杂！ - Simd

@Anush 我写了一个稍微长一点的解决方案，结果更快，也许更易读。你可以看一下。 - Olivier Melançon

Answer 1

使用 itertools

这里是一个使用itertools.groupby来检测峰值的简短解决方案。识别峰值的组被拆分，以产生实际序列。

from itertools import groupby, islice

l = [1, 2, 1, 2, 2, 0, 0]

fst, mid, nxt = groupby(l), islice(groupby(l), 1, None), islice(groupby(l), 2, None)
peaks = [[f[0], *m[1], n[0]] for f, m, n in zip(fst, mid, nxt) if f[0] < m[0] > n[0]]

print(peaks)

输出

[[1, 2, 1], [1, 2, 2, 0]]

使用循环（更快）

上面的解决方案很优雅，但由于创建了三个groupby的实例，所以需要遍历列表三次。

下面是一种使用单次遍历的解决方案。

def peaks(lst):
    first = 0
    last = 1
    while last < len(lst) - 1:
        if lst[first] < lst[last] == lst[last+1]:
            last += 1
        elif lst[first] < lst[last] > lst[last+1]:
            yield lst[first:last+2]
            first = last + 1
            last += 2
        else:
            first = last
            last += 1

l = [1, 2, 1, 2, 2, 0, 0]
print(list(peaks(l)))

输出

[[1, 2, 1], [1, 2, 2, 0]]

关于基准测试的注释

在使用timeit进行基准测试后，我发现使用循环的解决方案的性能提高了约20%。对于短列表，groupby的开销可能会将该数字提高到40％。此基准测试是在Python 3.6上完成的。

- Olivier Melançon

---

这个函数似乎缺少一个返回语句？ - Simd

@Anush 这是一个生成器，它会产生峰值。当列表可能相当长时，这是一个很好的实践。而且，生成器总是可以通过转换成列表来使用。 - Olivier Melançon

谢谢。你的回答很棒。 - Simd