Pythonで配列の「次に大きい要素」を求めるシンプルな実装を解説

本記事では、ユーザー定義関数を使って、配列内の各要素に対する「次に大きい要素(Next Greater Element)」を求めて出力する方法を解説します。

問題定義

与えられた配列の中で、各要素について「次に大きい要素」を出力します。ある要素 x の次に大きい要素とは、配列内で x よりも右側に存在する最初のより大きい要素のことです。右側により大きい要素が存在しない場合は、-1 を出力します。

入力テストケース

[12, 1, 2, 3]

出力

12 -> -1
1 -> 3
2 -> 3
3 -> -1

それでは、実際のソースコードを見ていきましょう。

実装例

# 次に大きい要素を求める関数
def elevalue(arr):
    # 配列を先頭から順に走査
    for i in range(0, len(arr)):
        # 現在位置以降のスライスから最大値を取得
        final = max(arr[i:])
        # 自身が最大値なら右側に大きい要素は存在しない
        if (arr[i] == final):
            print("%d -> %d" % (arr[i], -1))
        else:
            print("%d -> %d" % (arr[i], final))

# ドライバープログラム
def main():
    arr = [12, 1, 2, 3]
    elevalue(arr)
    arr = [1, 34, 2, 1]
    elevalue(arr)

if __name__ == '__main__':
    main()

出力結果

12 -> -1
1 -> 3
2 -> 3
3 -> -1
1 -> 34
34 -> -1
2 -> -1
1 -> -1

コードのポイント

この実装の鍵となるのは、スライス arr[i:] と組み込み関数 max() の組み合わせです。現在の要素から配列の末尾までをスライスして最大値を取得することで、右側に存在する最大の要素をシンプルに求められます。

現在の要素自身がその最大値と一致する場合、右側により大きい要素は存在しないため -1 を出力します。一致しない場合は、その最大値が「次に大きい要素」として出力されます。

なお、この方法は各要素ごとにスライスと最大値の計算を行うため、計算量は O(n²) となります。スタック(stack)を活用するアルゴリズムを採用すれば O(n) まで高速化できるため、大規模なデータを扱う場合はそちらの手法も検討するとよいでしょう。

まとめ

本記事では、ユーザー定義関数を活用して、配列内の各要素の「次に大きい要素」を求めるPythonの実装方法を学びました。スライスと max() 関数を組み合わせることで、直感的で読みやすいコードを実現できる点が魅力です。ぜひ自身の学習や実務にも応用してみてください。