Pythonで最も近い左と右の小さい要素間の最大の違いを見つける

したがって、入力がA =[3、5、9、8、8、10、4]の場合、出力は左側の要素として4になりますL =[0、3、5、5、5、8、3 ]、右要素R =[0、4、8、4、4、4、0]、最大絶対差L [i]-R [i] =8-4 =4

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

• 関数left_small_element（）を定義します。これにはA、tempが必要です

• n：=Aのサイズ

• スタック：=新しいリスト

• 0からnの範囲のiの場合、実行

  • スタックが空ではなく、スタックの最上位要素> =A [i]の場合、実行

    • スタックから最後の要素を削除する

  • スタックが空でない場合は、

    • temp [i]：=スタックの最上位要素

  • それ以外の場合

    • temp [i]：=0

  • スタックの最後にA[i]を挿入します

• メインの方法から、次のようにします-

• n：=Aのサイズ

• left：=サイズnのリストで0を入力

• right：=サイズnのリストで、0で埋めます

• left_small_element（A、left）

• left_small_element（反転A、右）

• res：=-1

• 0からnの範囲のiの場合、実行

  • res：=resの最大値、| left [i] --right [n-1-i] |

例

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

def left_small_element(A, temp):
   n = len(A)
   stack = []
   for i in range(n):
      while(stack != [] and stack[len(stack)-1] >= A[i]):
         stack.pop()
      if(stack != []):
         temp[i]=stack[len(stack)-1]
      else:
         temp[i]=0
      stack.append(A[i])
def find_maximum_difference(A):
   n = len(A)
   left=[0]*n
   right=[0]*n
   left_small_element(A, left)
   left_small_element(A[::-1], right)
   res = -1
   for i in range(n):
      res = max(res, abs(left[i] - right[n-1-i]))
   return res
A = [3, 5, 9, 8, 8, 10, 4]
print(find_maximum_difference(A))

入力

[3, 5, 9, 8, 8, 10, 4]

出力

4