पायथन में निकटतम बाएँ और दाएँ छोटे तत्वों के बीच अधिकतम अंतर खोजें

मान लीजिए कि हमारे पास पूर्णांकों की एक सरणी है; हमें सरणी में प्रत्येक तत्व के निकटतम बाएँ और दाएँ छोटे तत्व के बीच अधिकतम पूर्ण अंतर खोजना होगा। यदि किसी तत्व के दायीं ओर या बायीं ओर कोई छोटा तत्व नहीं है तो हम शून्य को छोटे तत्व के रूप में रखेंगे।

इसलिए, यदि इनपुट ए =[3, 5, 9, 8, 8, 10, 4] जैसा है, तो आउटपुट 4 होगा क्योंकि बाएं तत्व एल =[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 का आकार

• स्टैक :=एक नई सूची

• मेरे लिए 0 से n की सीमा में, करें

  • जबकि स्टैक खाली नहीं है और स्टैक का शीर्ष तत्व>=A[i], do

    • स्टैक से अंतिम तत्व हटाएं

  • अगर स्टैक खाली नहीं है, तो

    • अस्थायी [i]:=स्टैक का शीर्ष तत्व

  • अन्यथा,

    • अस्थायी [i]:=0

  • स्टैक के अंत में A[i] डालें

• मुख्य विधि से, निम्न कार्य करें -

• n :=A का आकार

• बायां:=आकार n की सूची और 0 से भरें

• दाएं:=आकार n की सूची और 0 से भरें

• left_small_element(A, left)

• left_small_element(उल्टा A, दाएँ)

• रेस :=-1

• मेरे लिए 0 से n की सीमा में, करें

  • रेस :=अधिकतम रेस, |बाएं[i] - दाएं[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