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

問題の概要

数値のリスト nums が与えられたとき、すべての「ピーク（山）」要素のインデックスを昇順で求めることを考えます。あるインデックス i の要素がピークであるためには、次の3つの条件がすべて満たされている必要があります。

1. 右側にある nums[i] と異なる値のうち最も近い数が存在しない、またはその値が nums[i] より小さい
2. 左側にある nums[i] と異なる値のうち最も近い数が存在しない、またはその値が nums[i] より小さい
3. 左側または右側のいずれかに、nums[i] と異なる値が少なくとも1つ存在する

例えば、入力が nums = [5, 8, 8, 8, 6, 11, 11] の場合、出力は [1, 2, 3, 5, 6] となります。これは、同じ値が連続する「プラトー（台地）」もピークとして扱うためです。つまり、8が並ぶ区間 [1, 2, 3] と、11が並ぶ区間 [5, 6] の両方がピークとみなされます。

解法のアプローチ

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

• n を nums のサイズとします
• 結果を格納する空のリスト ans を用意します
• i を 0 に初期化します
• i < n の間、以下を繰り返します
  • i0 := i とします
  • i < n かつ nums[i] == nums[i0] の間、i を1ずつ増やします（同じ値の連続区間をスキップ）
  • (i0 == 0 または nums[i0] > nums[i0 - 1]) かつ (i == n または nums[i0] > nums[i]) が成り立つ場合
    • i0 != 0 または i != n であるならば、範囲 [i0, i-1] を ans に追加します
• 最後に ans を返します

実装例

理解を深めるために、以下の実装例を見てみましょう。

def solve(nums):
    n = len(nums)
    ans = []
    i = 0
    while i < n:
        i0 = i
        while i < n and nums[i] == nums[i0]:
            i += 1
        if (i0 == 0 or nums[i0] > nums[i0 - 1]) and (i == n or nums[i0] > nums[i]):
            if i0 != 0 or i != n:
                ans.extend(range(i0, i))
    return ans

nums = [5, 8, 8, 8, 6, 11, 11]
print(solve(nums))

入力

[5, 8, 8, 8, 6, 11, 11]

出力

[1, 2, 3, 5, 6]

アルゴリズムのポイント

このアルゴリズムでは、まず同じ値が連続する区間（プラトー）をひとまとまりとして処理します。内側の while ループで、現在の値 nums[i0] と等しい要素をすべてスキップして区間の終端まで移動した後、区間の先頭が左隣の値より大きく、かつ区間の末尾が右隣の値より大きければ、その区間全体をピークとして記録します。

また、「i0 が 0 でない、または i が n でない」という条件により、リスト全体が同一の値で構成されている場合（左右どちらにも異なる値が存在しない場合）は、条件3に反するためピークとして扱われない点に注意してください。

計算量は O(n)、出力を除く追加メモリは O(1) であり、非常に効率的な手法です。