ค้นหาความแตกต่างสูงสุดระหว่างองค์ประกอบที่เล็กกว่าด้านซ้ายและขวาที่ใกล้ที่สุดใน Python

สมมติว่าเรามีอาร์เรย์ของจำนวนเต็ม เราต้องหาความแตกต่างสัมบูรณ์สูงสุดระหว่างองค์ประกอบที่เล็กกว่าทางซ้ายและทางขวาที่ใกล้ที่สุดของแต่ละองค์ประกอบในอาร์เรย์ หากไม่มีองค์ประกอบที่เล็กกว่าทางด้านขวาหรือด้านซ้ายขององค์ประกอบใดๆ เราจะใส่ศูนย์เป็นองค์ประกอบที่เล็กกว่า

ดังนั้น หากอินพุตเป็น A =[3, 5, 9, 8, 8, 10, 4] แล้วเอาต์พุตจะเป็น 4 ตามองค์ประกอบด้านซ้าย L =[0, 3, 5, 5, 5, 8, 3 ] องค์ประกอบที่ถูกต้อง R =[0, 4, 8, 4, 4, 4, 0], ความต่างสัมบูรณ์สูงสุด L[i] - R[i] =8 - 4 =4

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

• กำหนดฟังก์ชัน left_small_element() นี่จะใช้เวลา A ชั่วคราว

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

• stack :=รายการใหม่

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

  • ในขณะที่ stack ไม่ว่างและองค์ประกอบด้านบนของ stack>=A[i] ทำ

    • ลบองค์ประกอบสุดท้ายออกจากสแต็ก

  • ถ้าสแต็กไม่ว่างเปล่า

    • temp[i]:=องค์ประกอบด้านบนของสแต็ก

  • มิฉะนั้น

    • อุณหภูมิ[i]:=0

  • ใส่ A[i] ที่ส่วนท้ายของ stack

• จากวิธีหลัก ให้ทำดังนี้ −

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

• left:=รายการขนาด n และเติมด้วย 0

• right:=รายการขนาด n และเติม 0

• left_small_element(A, ซ้าย)

• left_small_element(กลับด้าน A, ขวา)

• res :=-1

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

  • res :=สูงสุดของความละเอียด |left[i] - right[n-1-i]|

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

def left_small_element(A, temp):
   n = len(A)
   stack = []
   for i in range(n):
      while(stack != [] and stack[len(stack)-1] >= A[i]):
         stack.pop()
      if(stack != []):
         temp[i]=stack[len(stack)-1]
      else:
         temp[i]=0
      stack.append(A[i])
def find_maximum_difference(A):
   n = len(A)
   left=[0]*n
   right=[0]*n
   left_small_element(A, left)
   left_small_element(A[::-1], right)
   res = -1
   for i in range(n):
      res = max(res, abs(left[i] - right[n-1-i]))
   return res
A = [3, 5, 9, 8, 8, 10, 4]
print(find_maximum_difference(A))

อินพุต

[3, 5, 9, 8, 8, 10, 4]

ผลลัพธ์

4