Pythonで数値リスト内のローカルピーク（山）のインデックスをすべて見つける方法

ローカルピークとは？

長さ2以上の数値リスト nums が与えられたとき、リスト内に存在するすべての「ピーク（山）」のインデックスを求める問題を考えます。

あるインデックス i がピークであるとは、以下のいずれかの条件を満たす場合を指します。

• i = 0 の場合：nums[i] > nums[i + 1]
• i = n - 1 の場合：nums[i] > nums[i - 1]
• 上記以外の場合：nums[i - 1] < nums[i] > nums[i + 1]

つまり、リストの端にある要素は隣接する1つの要素より大きければピークとみなされ、それ以外の要素は両側の隣接要素のどちらよりも大きい場合にピークとなります。

具体例

たとえば、入力が nums = [5, 6, 7, 6, 9] の場合、出力は [2, 4] になります。これは、インデックス2の要素「7」が両隣の「6」「6」より大きく、インデックス4の要素「9」が左隣の「6」より大きいためです。

解法のアプローチ

この問題は、リストを先頭から順に走査しながら、各要素がピークの条件を満たすかどうかを判定することで解けます。手順は以下の通りです。

• 結果を格納するための空リスト ans を用意する
• リストの長さを n とする
• n が1の場合は、比較対象となる隣接要素が存在しないため、空リストを返す
• enumerate() を使って、各インデックス i と値 num を順に処理する
  • i が先頭でも末尾でもない場合（0 < i < n - 1）：両隣の要素より大きければ i を ans に追加する
  • i = 0 の場合：右隣の要素より大きければ i を ans に追加する
  • i = n - 1 の場合：左隣の要素より大きければ i を ans に追加する
• 最後に ans を返す

Python実装例

以下に、このアルゴリズムを実装したコードを示します。

def solve(nums):
    ans = []
    n = len(nums)

    if n == 1:
        return ans

    for i, num in enumerate(nums):
        if i > 0 and i < n - 1:
            if nums[i - 1] < num > nums[i + 1]:
                ans.append(i)

        if i == 0:
            if num > nums[i + 1]:
                ans.append(i)

        if i == n - 1:
            if num > nums[i - 1]:
                ans.append(i)

    return ans

nums = [5, 6, 7, 6, 9]
print(solve(nums))

入力

[5, 6, 7, 6, 9]

出力

[2, 4]

計算量について

このアルゴリズムはリストを一度だけ走査するため、時間計算量は O(n) です。また、結果を格納するリスト以外に余分なメモリを必要としないため、空間計算量も効率的です。シンプルな線形探索だけでピークをすべて検出できる、実用的な解法と言えるでしょう。