假设我们有一个称为nums的数字列表，我们必须找到任何数字与下一个较小数字之间存在的最大差。我们的目标是在线性时间内解决这个问题。
因此，如果输入类似于nums = [14、2、6、35、12]，则输出将为21，因为35和14的最大差值为21。
为了解决这个问题，我们将遵循以下步骤-
max_val：=最大值，min_val：=最小值
如果max_val与min_val相同，则
返回0
delta：=（max_val − min_val）/（nums − 1的大小）
min_map：=一个空的映射（如果某些值不存在，则返回值为inf）
max_map：=一个空映射（如果某些值不存在，则返回值为-inf）
res：= 0，idx：= 0
对于nums中的每个num，执行
idx：=（（（num − min_val）/ delta）的下限
max_map [idx]：= max_map [idx]和num的最大值
min_map [idx]：= min_map [idx]和num的最小值
prev：= min_val
对于0到nums-1范围内的i
res：= res的最大值和（min_map [i] −上一页）
上一个：= max_map [i]
如果min_map [i]与inf不同，则
返回res
让我们看下面的实现以更好地理解-
from collections import defaultdict
import math
class Solution:
def solve(self, nums):
max_val = max(nums)
min_val = min(nums)
if max_val == min_val:
return 0
delta = (max_val − min_val) / (len(nums) − 1)
min_map = defaultdict(lambda: float("inf"))
max_map = defaultdict(lambda: float("−inf"))
res = 0
idx = 0
for num in nums:
idx = math.floor((num − min_val) / delta)
max_map[idx] = max(max_map[idx], num)
min_map[idx] = min(min_map[idx], num)
prev = min_val
for i in range(len(nums)):
if min_map[i] != float("inf"):
res = max(res, min_map[i] − prev)
prev = max_map[i]
return res
ob = Solution()
nums = [14, 2, 6, 35, 12]
print(ob.solve(nums))[14, 2, 6, 35, 12]
输出结果
21