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

Cho mảng, tìm phần tử mà tất cả phần tử trước nó nhỏ hơn nó, và tất cả phần tử sau nó lớn hơn nó. Trả về chỉ số, nếu không có trả về -1.

Ví dụ: [6,2,5,4,7,9,11,8,10] → chỉ số 4 (giá trị 7).

Giải thuật

• Tính mảng maximum_left[i] = max của các phần tử từ 0 đến i-1.
• Duyệt từ phải sang trái, giữ minimum_right = min các phần tử từ i+1 đến cuối.
• Nếu maximum_left[i] < arr[i] < minimum_right → trả về i.

Ví dụ

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] < minimum_right:
            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