หาองค์ประกอบที่ทุกค่าด้านซ้ายน้อยกว่า และด้านขวาใหญ่กว่าใน Python

สมมติว่าเรามีอาร์เรย์ ต้องการหาองค์ประกอบที่ทุกค่าด้านซ้ายน้อยกว่ามัน และทุกค่าด้านขวาใหญ่กว่ามัน คืนค่าดัชนี หากไม่มี คืนค่า -1

เช่น A = [6, 2, 5, 4, 7, 9, 11, 8, 10] ผลลัพธ์คือ 4 (ค่า 7)

ขั้นตอนการแก้ปัญหา

1. สร้างอาร์เรย์ max_left โดย max_left[i] = max(max_left[i-1], arr[i-1])
2. ตั้ง min_right = infinity
3. วนลูปจากขวาไปซ้าย:
   • ถ้า max_left[i] < arr[i] and min_right > arr[i] คืนค่า i
   • อัปเดต min_right = min(min_right, arr[i])

ตัวอย่างโค้ด Python

def get_element(arr):
    n = len(arr)
    max_left = [None] * n
    max_left[0] = float('-inf')
    for i in range(1, n):
        max_left[i] = max(max_left[i-1], arr[i-1])
    min_right = float('inf')
    for i in range(n-1, -1, -1):
        if max_left[i] < arr[i] and min_right > arr[i]:
            return i
        min_right = min(min_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