Python:列表中元素之间的最大差异
Python:列表中元素之间的最大差异
提问于 2018-10-29 08:21:42
如果当前元素右侧的元素更大，则需要在未排序列表中找到元素之间的最大差异。例如：
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)) 我的问题是第二个解决方案是对的吗？如果是的话，那是最优的吗？这两个函数的时间复杂度是多少？还有其他更好的解决方案吗？
回答 4
Stack Overflow用户
回答已采纳
发布于 2018-10-29 11:25:24
第二个解决方案仍然在每次迭代中重新计算前缀列表的最大值，这是您不需要做的。
我认为这两种解决方案都是正确的，但是第二种解决方案至少仍然是二次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)。
Stack Overflow用户
发布于 2021-10-31 17:06:10
使用新的walrus运算符(Python >3.8req)
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)Stack Overflow用户
发布于 2019-12-12 12:32:01
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)))页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/53041365
复制相关文章
相似问题
腾讯云开发者
