在 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 的大小

  • stack := 一個新的列表

  • 對於 i 從 0 到 n 的範圍，執行以下操作

    • 當 stack 不為空且 stack 的頂部元素 >= A[i] 時，執行以下操作

      • 從 stack 中刪除最後一個元素

    • 如果 stack 不為空，則

      • temp[i]:= stack 的頂部元素

    • 否則，

      • temp[i]:= 0

    • 將 A[i] 插入到 stack 的末尾

  • 從主方法中執行以下操作 -

  • n := A 的大小

  • left:= 一個大小為 n 的列表，並用 0 填充

  • right:= 一個大小為 n 的列表，並用 0 填充

  • left_small_element(A, left)

  • left_small_element(反轉 A, right)

  • res := -1

  • 對於 i 從 0 到 n 的範圍，執行以下操作

    • 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

更新於: 2020年8月25日

186 次檢視

開啟你的 職業生涯

透過完成課程獲得認證

開始
廣告