すべての要素がそれよりも小さく、その後すべてがPythonで大きくなる要素を見つけます

配列があるとすると、すべての要素がそれよりも小さく、その後はすべてがそれよりも大きい要素を見つける必要があります。最後に、要素のインデックスを返します。そのような要素がない場合は、-1を返します。

したがって、入力がA-[6、2、5、4、7、9、11、8、10]の場合、出力は4になります。

これを解決するには、次の手順に従います-

• n：=arrのサイズ

• maximum_left：=サイズnの配列

• maximum_left [0]：=-infinity

• 1からnの範囲のiの場合、実行します

  • maximum_left [i]：=maximum_left [i-1]の最大値、arr [i-1]

• minimum_right：=無限大

• n-1から-1の範囲のiの場合、1ずつ減少します

  • maximum_left [i]arr[i]の場合、

    • iを返す

  • minimum_right：=最小値のminimum_right、arr [i]

    • -1を返す

例

理解を深めるために、次の実装を見てみましょう-

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