Python：列表中元素之间的最大差异

Question

如果当前元素右侧的元素更大，我需要找到未排序列表中元素之间的最大差异。例如：

 myList = [2, 3, 8, 0, 7].

函数应计算如下：

 present element = 2.
is 3 > 2? Yes. Then 3-2 = 1
is 8 > 2? Yes. Then 8-2 = 6
is 0 > 2? No. Go to the next element.
is 7 > 2? Yes. Then 7-2 = 5 and so on

Finally my output = 7

我的第一个解决方案如下：

 def maxDiff(a):
l = len(a)
arr = []
for i in range(l-1):
    for j in range(i+1, l):
        if a[j] > a[i]:
            diff = a[j] - a[i]
            arr.append(diff)
return (max(arr))

有人说这不是最佳解决方案。我想出了另一个解决方案，如下所示：

 def maxDiff(a):
l = len(a)
diffList = []
for i in range(l-1):
    newList = a[i+1:]
    max1 = max(newList)
    difference = max1 - a[i]
    diffList.append(difference)
return (max(diffList))

我的问题是第二个解决方案是否正确？如果是，那么它是最优的吗？这两个函数的时间复杂度是多少？还有其他更优的解决方案吗？

原文由 Lax_Sam 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

您的第二个解决方案仍然会在每次迭代时重新计算前缀列表的最大值，您不需要这样做。

我认为你的两个解决方案都是正确的，但第二个仍然至少是二次 O(n^2) 因为你在 for 循环中执行线性时间操作（例如 max() ）。所以回答你的问题：不，这可能不是最佳解决方案。

如果我正确地理解了这个问题，它可以使用 动态规划 来解决。考虑以下代码：

 def maxDiff(a):
    vmin = a[0]
    dmax = 0
    for i in range(len(a)):
        if (a[i] < vmin):
            vmin = a[i]
        elif (a[i] - vmin > dmax):
            dmax = a[i] - vmin
    return dmax

在这里，我们只是简单地跟踪到目前为止遇到的最小值和最大差异，从而允许我们在列表中仅迭代一次，而无需存储任何额外的列表或进行任何嵌套循环。因此，就比较操作而言，它的运行时间应该是线性的，O(n)。

原文由 Berthur 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

使用新的海象运算符（Python >3.8 要求）

     import sys
    lst = [7,1,5,4]

    minscan = sys.maxsize
    solution = max([x - (minscan := min(minscan,x)) for x in lst])
    print(solution if solution !=0 else -1)

原文由 avx 发布，翻译遵循 CC BY-SA 4.0 许可协议