मान लीजिए हमारे पास पूर्णांकों की एक सरणी है; हमें सरणी में प्रत्येक तत्व के निकटतम बाएं और दाएं छोटे तत्व के बीच अधिकतम निरपेक्ष अंतर ढूंढना है। यदि किसी तत्व के दाएं या बाएं हाथ पर कोई छोटा तत्व नहीं है तो हम छोटे तत्व के रूप में शून्य रखेंगे।
तो, यदि इनपुट 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 का आकार
stack := एक नई सूची
i के लिए 0 से n की सीमा में, करें
जब तक stack खाली नहीं है और stack का शीर्ष तत्व >= A[i], करें
stack से अंतिम तत्व हटाएं
यदि stack खाली नहीं है, तो
temp[i] := stack का शीर्ष तत्व
अन्यथा,
temp[i] := 0
stack के अंत में A[i] डालें
मुख्य विधि से, निम्नलिखित करें -
n := A का आकार
left := n आकार की एक सूची और 0 से भरें
right := n आकार की एक सूची और 0 से भरें
left_small_element(A, left)
left_small_element(उल्टी A, right)
res := -1
i के लिए 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
