Pythonで「左側はすべて小さく、右側はすべて大きい」条件を満たす要素を見つける方法

配列が与えられたとき、「その要素より前にあるすべての要素が小さく、後ろにあるすべての要素が大きい」という条件を満たす要素を見つける問題を考えてみましょう。該当する要素が存在すればそのインデックスを返し、存在しない場合は -1 を返します。

例えば、入力が A = [6, 2, 5, 4, 7, 9, 11, 8, 10] の場合、出力は 4 になります。インデックス 4 の要素「7」の左側には 7 未満の値（6, 2, 5, 4）のみが並び、右側には 7 より大きい値（9, 11, 8, 10）のみが並んでいるためです。

解法のアプローチ

この問題を効率的に解くには、以下の手順に従います。

1. n に配列 arr のサイズを代入します。
2. サイズ n の配列 maximum_left を用意します。maximum_left[i] には、インデックス i より左側にある要素の最大値が格納されます。
3. maximum_left[0] に負の無限大（-inf）を設定します（左側に要素が存在しないため）。
4. i を 1 から n-1 まで順に処理しながら、maximum_left[i] = max(maximum_left[i-1], arr[i-1]) と更新していきます。
5. minimum_right を正の無限大（inf）で初期化します。この変数には、現在位置より右側にある要素の最小値が保持されます。
6. i を n-1 から 0 まで逆順に走査し、maximum_left[i] < arr[i] かつ minimum_right > arr[i] が成立すれば、その i を返します。
7. 条件を満たさない場合は、minimum_right = min(minimum_right, arr[i]) と更新して処理を続けます。
8. 最後まで条件を満たす要素が見つからなければ、-1 を返します。

実装例

理解を深めるために、以下の Python コードをご覧ください。

def get_element(arr):
    n = len(arr)
    maximum_left = [None] * n
    maximum_left[0] = float('-inf')
    for i in range(1, n):
        maximum_left[i] = max(maximum_left[i-1], arr[i-1])
    minimum_right = float('inf')
    for i in range(n-1, -1, -1):
        if maximum_left[i] < arr[i] and minimum_right > arr[i]:
            return i
        minimum_right = min(minimum_right, arr[i])
    return -1

arr = [6, 2, 5, 4, 7, 9, 11, 8, 10]
print(get_element(arr))

入力

[6, 2, 5, 4, 7, 9, 11, 8, 10]

出力

4

計算量の分析

このアルゴリズムでは、まず左側最大値の配列を構築するのに O(n)、続いて右側からの走査にも O(n) の計算が必要となるため、全体の時間計算量は O(n) になります。各要素について左右を毎回確認する素朴な全探索（O(n²)）と比べて大幅な高速化が可能です。ただし、maximum_left 配列の分だけ O(n) の追加メモリが必要になる点には注意してください。