資料結構
網路
關係型資料庫管理系統 (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 次檢視
廣告