数据结构
网络
关系型数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究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 中的每个数字，执行以下操作：
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，执行以下操作：
如果 min_map[i] 与 inf 不相同，则
res := 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))输入
[14, 2, 6, 35, 12]
输出
21
更新于：2020年12月26日
237 次查看
广告