পাইথনে নিকটতম বাম এবং ডান ছোট ছোট উপাদানগুলির মধ্যে সর্বাধিক পার্থক্য খুঁজুন

ধরুন আমাদের পূর্ণসংখ্যার একটি অ্যারে আছে; আমাদের অ্যারের প্রতিটি উপাদানের নিকটতম বাম এবং ডান ছোট উপাদানের মধ্যে সর্বাধিক পরম পার্থক্য খুঁজে বের করতে হবে। যদি কোন উপাদানের ডানদিকে বা বাম দিকে কোন ছোট উপাদান না থাকে তাহলে আমরা শূন্যকে ছোট উপাদান হিসেবে রাখব।

সুতরাং, যদি ইনপুটটি 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, temp

  লাগবে

• n :=A

  এর আকার

• স্ট্যাক :=একটি নতুন তালিকা

• 0 থেকে n রেঞ্জের জন্য, করুন

  • যখন স্ট্যাক খালি না থাকে এবং স্ট্যাকের শীর্ষ উপাদান>=A[i], do

    • স্ট্যাক থেকে শেষ উপাদান মুছুন

  • যদি স্ট্যাক খালি না হয়, তাহলে

    • temp[i]:=স্ট্যাকের শীর্ষ উপাদান

  • অন্যথায়,

    • temp[i]:=0

  • স্ট্যাকের শেষে A[i] ঢোকান

• প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -

• n :=A

  এর আকার

• left:=n আকারের একটি তালিকা এবং 0

  দিয়ে পূরণ করুন

• ডান:=আকার n এর একটি তালিকা এবং 0

  দিয়ে পূরণ করুন

• left_small_element(A, left)

• left_small_element(উল্টানো A, ডানে)

• res :=-1

• 0 থেকে n রেঞ্জের জন্য, করুন

  • res :=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