ค้นหาองค์ประกอบก่อนที่องค์ประกอบทั้งหมดจะเล็กกว่าและหลังจากนั้นทั้งหมดจะยิ่งใหญ่กว่าในPython

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

ดังนั้น หากอินพุตเป็น A - [6, 2, 5, 4, 7, 9, 11, 8, 10] เอาต์พุตจะเป็น 4

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• n :=ขนาดของ arr

• maximum_left :=อาร์เรย์ขนาด n

• maximum_left[0] :=-อินฟินิตี้

• สำหรับผมอยู่ในช่วง 1 ถึง n ทำ

  • maximum_left[i] :=maximum of maximum_left[i-1], arr[i-1]

• maximum_right :=อินฟินิตี้

• สำหรับฉันอยู่ในช่วง n-1 ถึง -1 ลดลง 1 ทำ

  • ถ้า maximum_left[i] arr[i] แล้ว

    • กลับมา

  • maximum_right :=ขั้นต่ำของ maximum_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