在 Python 中查詢一個元素，該元素之前的所有元素都小於它，之後的所有元素都大於它

假設我們有一個數組，我們需要找到一個元素，在其之前的所有元素都小於它，在其之後的所有元素都大於它。最後，返回該元素的索引，如果沒有這樣的元素，則返回 -1。

因此，如果輸入類似於 A - [6, 2, 5, 4, 7, 9, 11, 8, 10]，則輸出為 4。

為了解決這個問題，我們將遵循以下步驟：

  • n := arr 的大小

  • maximum_left := 一個大小為 n 的陣列

  • maximum_left[0] := -∞

  • 對於 i 從 1 到 n，執行：

    • maximum_left[i] := maximum_left[i-1] 和 arr[i-1] 中的較大者

  • minimum_right := ∞

  • 對於 i 從 n-1 到 -1，遞減 1，執行：

    • 如果 maximum_left[i] < arr[i] 且 minimum_right > 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

更新於：2020年8月19日

408 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告