Pythonで任意の数と次に小さい数の最大差を線形時間O(n)で求めるプログラム

数値のリスト nums が与えられたとき、リスト内の任意の数と、それより小さい直近の数との間の最大差を求めることを考えます。この問題は、ソートに頼らず線形時間 O(n) で解くことが目標です。

たとえば、入力が nums = [14, 2, 6, 35, 12] の場合、出力は 21 になります。これは 35 と 14 の差が最も大きいためです。

解法のアプローチ：バケット分割の活用

この問題を線形時間で解く鍵となるのは「鳩の巣原理」に基づくバケット分割です。要素数を n、値の範囲を [min_val, max_val] とすると、最大差は少なくとも (max_val − min_val) / (n − 1) 以上になることが保証されます。そこで値域を等間隔のバケットに分け、各バケットごとに最小値と最大値だけを記録すれば、隣接するバケット間の差を調べるだけで答えが得られます。

アルゴリズムの手順

• 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 := floor((num − min_val) / delta)(num が属するバケット番号)
  • max_map[idx] := max(max_map[idx], num)
  • min_map[idx] := min(min_map[idx], num)
• prev := min_val とする
• i を 0 から nums の要素数 − 1 まで繰り返す:
  • min_map[i] が inf でない場合(バケットが空でない場合):
    • res := max(res, min_map[i] − prev)
    • prev := max_map[i]
• res を返す

なぜこの方法で正しく求まるのか?

バケットの幅を delta とすると、同じバケット内の2つの数の差は必ず delta 未満になります。一方、求めるべき最大差は理論上 delta 以上であるため、答えは必ず異なるバケットにまたがるペアから生じます。したがって、各バケットの最小値・最大値のみを保持し、空でない隣接バケット同士について「前のバケットの最大値」と「現在のバケットの最小値」の差を順に確認していけば、全体の最大差を取りこぼしなく求められます。

計算量は、初期化・バケットへの振り分け・最終走査のすべてが O(n)、追加で必要なメモリも O(n) です。

実装例

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