Pythonで任意の数とその次に小さい数の最大差を見つけるプログラム

numsと呼ばれる数のリストがあるとすると、任意の数と次に小さい数の間に存在する最大の差を見つける必要があります。私たちの目標は、これを線形時間で解決することです。

したがって、入力がnums =[14、2、6、35、12]のようである場合、35と14の差が21であるため、出力は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の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の場合、実行します

  • 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]

出力

21