Pythonで配列内の要素を検索し、厳密に減少した後に増加するシーケンスを形成する方法

正の数からなる配列が与えられたとき、「最初に厳密に減少するシーケンスが続き、その後に厳密に増加する整数のシーケンスが続く」という形状を作り出す転換点（要素）を見つける問題を考えてみましょう。この問題には以下の条件があります。

• 各シーケンス（減少部分・増加部分）は最小長2以上である必要がある
• 減少シーケンスの最後の値は、増加シーケンスの最初の値と一致すること

例えば、入力が {5, 4, 3, 4} の場合、出力は 3 になります。{5, 4, 3} が厳密に減少しており、続いて {3, 4} が厳密に増加しているためです。

解法のアプローチ

この問題を解くために、以下の手順に従います。

• カウンター increase := 1、decrease := 1 を初期化する
• n := 配列のサイズ とする
• i を 1 から n まで繰り返す
  • array[i] < array[i-1] の場合：
    • increase == 1 ならば、decrease := decrease + 1
    • そうでなければ、-1 を返す
  • array[i] > array[i-1] の場合：
    • increase == 1 ならば、pt := array[i-1]（転換点を記録）
    • decrease >= 2 ならば、increase := increase + 1
    • そうでなければ、-1 を返す
  • array[i] == array[i-1] の場合：
    • -1 を返す（等しい値は許されない）
• ループ終了後、increase >= 2 かつ decrease >= 2 ならば pt を返す
• それ以外の場合は -1 を返す

実装例

理解を深めるために、以下のPythonコードを見てみましょう。

def search_element(array):
   increase = 1
   decrease = 1
   n = len(array)
   for i in range(1, n):
      if(array[i] < array[i-1]):
         if increase == 1:
            decrease = decrease + 1
         else:
            return -1
      elif(array[i] > array[i-1]):
         if increase == 1:
            pt = array[i-1]
         if decrease >= 2:
            increase = increase + 1
         else:
            return -1
      elif(array[i] == array[i-1]):
         return -1
   if(increase >= 2 and decrease >= 2):
      return pt
   else:
      return -1
array = [5,4,3,4]
element = search_element(array)
print(element)

入力

[5,4,3,4]

出力

3

このアルゴリズムは配列を一度だけ走査するため、時間計算量は O(n)、追加のメモリ使用量は O(1) という効率的な性能を持ちます。隣接する要素が等しい場合や、減少→増加のパターンが崩れた場合には即座に -1 を返すことで、条件を満たさない配列を素早く判定できる点もポイントです。