Tìm phần tử trước đó tất cả các phần tử nhỏ hơn nó và sau đó tất cả các phần tử đều lớn hơn trong Python

Giả sử chúng ta có một mảng, chúng ta phải tìm một phần tử mà trước đó tất cả các phần tử đều nhỏ hơn nó và sau đó tất cả các phần tử đều lớn hơn nó. Cuối cùng, trả về chỉ mục của phần tử, nếu không có phần tử nào như vậy thì trả về -1.

Vì vậy, nếu đầu vào là A - [6, 2, 5, 4, 7, 9, 11, 8, 10], thì đầu ra sẽ là 4.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của arr

• Maximum_left:=một mảng có kích thước n

• max_left [0]:=-infinity

• đối với tôi trong phạm vi từ 1 đến n, hãy thực hiện

  • max_left [i]:=tối đa của Maximum_left [i-1], arr [i-1]

• Minim_right:=infinity

• đối với tôi trong phạm vi n-1 đến -1, giảm 1, thực hiện

  • nếu Maximum_left [i] arr [i], thì

    • trả lại tôi

  • Minim_right:=tối thiểu của Minimum_right, arr [i]

    • trả về -1

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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))

Đầu vào

[6, 2, 5, 4, 7, 9, 11, 8, 10]

Đầu ra

4