Pythonでグローバル反転とローカル反転の数が一致しているかを判定するプログラム

問題の概要

重複のない数値のリスト nums が与えられたとします。グローバル反転(global inversion)とは、i < j かつ nums[i] > nums[j] を満たすインデックスの組 (i, j) が存在することを指します。一方、ローカル反転(local inversion)とは、隣接するインデックス i と i + 1 の間で nums[i] > nums[i + 1] が成り立つことです。

この記事では、グローバル反転の総数とローカル反転の総数が一致しているかどうかを判定するプログラムを紹介します。

たとえば、入力が nums = [3, 2, 4] の場合、出力は True になります。これは、インデックス 0 と 1 のペアがグローバル反転であると同時にローカル反転でもあり、それ以外に反転が存在しないためです。

解法のポイント

重要な性質として、すべてのローカル反転は必ずグローバル反転でもあるという点が挙げられます。したがって、両者の数が等しくなるのは、「インデックスの差が 2 以上離れた要素の間に反転(非ローカルなグローバル反転)がひとつも存在しない」場合に限られます。

この性質を利用すると、配列全体の反転を数え上げる必要はなく、j ≥ i + 2 となる nums[i] > nums[j] の組み合わせが存在しないかを確認するだけでよいことが分かります。

アルゴリズムの手順

• l を nums のサイズとする
• i を 0 から l - 3 まで繰り返す:
  • j を i + 2 から l - 1 まで繰り返す:
    • nums[i] > nums[j] であれば False を返す
• ループを抜けたら True を返す

実装例

以下がPythonでの実装です。

class Solution:
    def solve(self, nums):
        l = len(nums)
        for i in range(l - 2):
            for j in range(i + 2, l):
                if nums[i] > nums[j]:
                    return False
        return True

ob = Solution()
nums = [3, 2, 4]
print(ob.solve(nums))

入力

[3, 2, 4]

出力

True

計算量の改善:O(n) への最適化

上記の二重ループによる手法の計算量は O(n²) です。しかし、「各要素は、自分より 2 つ以上前に位置する要素の最大値より小さくなってはならない」という条件を先頭から順にチェックすれば、O(n) まで高速化できます。

class Solution:
    def solve(self, nums):
        max_val = float('-inf')
        for i in range(len(nums)):
            if nums[i] < max_val:
                return False
            if i >= 1:
                max_val = max(max_val, nums[i - 1])
        return True

この実装では、変数 max_val が常に「現在の要素から 2 つ以上前までの最大値」を保持するため、非ローカルなグローバル反転を線形時間で検出できます。

まとめ

ローカル反転はすべてグローバル反転に含まれるため、両者の数が等しいかどうかは「距離 2 以上の反転の有無」だけで判定できます。シンプルな二重ループで O(n²)、最大値を追跡する方法で O(n) に削減できる点は、競技プログラミングや実務においても役立つテクニックなので覚えておきましょう。