在Python中找出任何数字和其下一个更小数字之间的最大差的程序

假设我们有一个名为nums的数字列表，我们必须找到任何数字和下一个更小数字之间存在的最大差异。我们的目标是在线性时间内解决这个问题。

因此，如果输入为nums = [14, 2, 6, 35, 12]，则输出将为21，因为35和14的差异最大为21。

要解决此问题，我们将按照以下步骤进行−

max_val：nums的最大值，min_val：nums的最小值
如果max_val与min_val相同，则
- 返回0
delta：（max_val-min_val）/（nums大小-1）
min_map：一个空映射（如果某些值不存在，则返回inf）
max_map：一个空映射（如果某些值不存在，则返回-inf）
res：0，idx：0
对于nums中的每个数字，请执行以下操作
- 索引：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
对于0到nums大小-1的范围，即i，执行以下操作
- 如果min_map [i]不等于inf，则
  - res：max（res，min_map [i] – prev）
  - prev： max_map [i]
返回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))