Pythonでソート済みリストの隣接要素間の最大ギャップを求める方法

はじめに

本記事では、数値のリスト nums が与えられたとき、そのリストをソートした状態における隣接する2つの要素の差（ギャップ）の中で最も大きい値を求める方法を解説します。

例えば、入力が [5, 2, 3, 9, 10, 11] の場合を考えてみましょう。このリストを昇順にソートすると [2, 3, 5, 9, 10, 11] となり、隣接要素同士の差はそれぞれ「1, 2, 4, 1, 1」になります。したがって、最大のギャップは 5 と 9 の間の 4 となり、出力は 4 です。

解決のアプローチ

この問題は以下の手順で解くことができます。

• まず、リスト nums を昇順にソートします。
• 隣接する要素同士の差を格納するための空のリストを用意します。
• ソート済みリストの先頭から末尾までループ処理を行い、各位置 i について n[i+1] - n[i]（次の要素と現在の要素の差）を計算してリストに追加します。
• 最後に、差のリストの中から最大値を返します。

実装例

それでは、実際のコードを見てみましょう。

class Solution:
    def solve(self, nums):
        n = sorted(nums)
        ans = []
        for i in range(len(n)-1):
            ans.append(n[i+1]-n[i])
        return max(ans)

ob = Solution()
nums = [5, 2, 3, 9, 10, 11]
print(ob.solve(nums))

入力

[5, 2, 3, 9, 10, 11]

出力

4

コードのポイント

この実装では、Pythonの組み込み関数 sorted() を使うことで、元のリストを変更せずに新しいソート済みリストを作成しています。その後、range(len(n)-1) を使って隣接要素のペアをすべて走査し、差分を収集します。最後に max() 関数で最大の差を取得しています。

なお、より簡潔に書きたい場合は、リスト内包表記を使って以下のように1行で差分のリストを作成することも可能です。

def solve(self, nums):
    n = sorted(nums)
    return max(b - a for a, b in zip(n, n[1:]))

計算量について

このアルゴリズムの時間計算量は、ソート処理が支配的となるため O(n log n) です。差分の計算と最大値の探索はそれぞれ O(n) で完了します。要素数が多いリストでも効率的に動作するため、実用的なアプローチと言えます。

まとめ

リストをソートして隣接要素の差を比較するというシンプルな手法で、最大ギャップを容易に求めることができます。インタビュー問題やデータ分析の場面でも応用できる基本的なテクニックなので、ぜひマスターしておきましょう。