程序以查找Python中任意数字及其下一个较小数字的最大差

Z时代
2024-01-10
分类：综合

假设我们有一个称为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))