Python에서 임의의 숫자와 그 다음 작은 숫자의 최대 차이를 찾는 프로그램

<시간/>

nums라는 숫자 목록이 있다고 가정하고 임의의 숫자와 그 다음으로 작은 숫자 사이에 존재하는 최대 차이를 찾아야 합니다. 우리의 목표는 이것을 선형 시간에 푸는 것입니다.

따라서 입력이 nums =[14, 2, 6, 35, 12]와 같으면 35와 14의 차이가 21로 가장 크므로 출력은 21이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

max_val :=최대 숫자, min_val :=최소 숫자
max_val이 min_val과 같으면
- 0 반환
델타 :=(max_val - min_val) / (숫자의 크기 - 1)
min_map :=빈 맵(일부 값이 없으면 inf로 반환 값)
max_map :=빈 맵(일부 값이 없으면 -inf로 반환 값)
해상도 :=0, IDx :=0
숫자의 각 숫자에 대해 수행
- idx :=((num − min_val) / delta)
  의 바닥
- max_map[idx] :=max_map[idx] 및 num의 최대값
- min_map[idx] :=min_map[idx] 및 num의 최소값
이전 :=min_val
범위 0에서 nums - 1의 크기에 있는 i에 대해 다음을 수행합니다.
- min_map[i]이 inf와 같지 않으면
  - res :=최대 res 및 (min_map[i] − prev)
  - 이전 :=max_map[i]
반환 해상도

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예시

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]