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

---

可能有一些方法可以避免每次重新计算最大值，例如缓存。 - Tim Rutter

我没有使用 diffList 数组，但是我得到了正确的结果。我正在寻找一种方法，不用每次计算最大值。@TimRutter - Lax_Sam

@Dave OP有一个额外的要求：“……如果当前元素右侧的元素更大。例如，maxDiff([9,1,2])应该是1，而不是8。” - Berthur

print(max(a)-min(a))有什么问题？ - srinath samala

请查看"哪个网站？"以获取一般问题和"是否适合Code Review？"。 - Prune

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

---

一个警告：当数组严格降序时，未指定算法应该执行什么操作。在这种情况下，原帖的第一个算法将会崩溃，第二个算法将产生负数（不正确）的结果，而这个算法将简单地返回0。您可能需要通过检查来单独处理这种情况。 - Berthur

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

---

也在https://youtu.be/UogkQ67d0nY中解释 - avx

Answer 3

虽然解决一个问题有很多方法，但我建议这种方式会更快一点，并且符合Python的风格。

mylist = [2, 3, 8, 0, 7]
max_diff = max( [mylist[i+1]-mylist[i] for i in range(len(mylist)-1) if mylist[i]<mylist[i+1]] )

print(max_diff)

- Shahir Ansari

Answer 4

def maxPairDiff(arr):
    listDiff=[]
    for p,i in enumerate(arr):
        evalList=[e for e in arr[p+1:] if e>i]
        if len(evalList)>0:
            listDiff.append(max(evalList)-i)
    return (max(listDiff))


givenList = [7, 9, 5, 6, 3, 2]
print ("Required result is {}".format(maxPairDiff(givenList)))

- vikashkmr3188