পাইথনে অ্যারে-এর নিকটতম বাম ও ডান ছোট উপাদানের পার্থক্যের সর্বোচ্চ মান বের করা

ধরা যাক একটি ইন্টিজার অ্যারে আছে। প্রতিটি উপাদানের জন্য তার নিকটতম বাম এবং ডান পাশের ছোট উপাদান বের করতে হবে। যদি কোনো পাশে ছোট উপাদান না থাকে তবে 0 ধরা হবে। তারপর বাম ও ডান ছোট উপাদানের absoluta পার্থক্যের সর্বোচ্চ মান বের করতে হবে।

যেমন, A=[3,5,9,8,8,10,4] হলে বাম ছোট: [0,3,5,5,5,8,3], ডান ছোট: [0,4,8,4,4,4,0], সর্বোচ্চ পার্থক্য = 8-4=4।

সমাধানের ধাপসমূহ (স্ট্যাক ব্যবহার)

• left_small_element(A, temp) ফাংশন: স্ট্যাক ব্যবহার করে প্রতিটি উপাদানের নিকটতম বাম ছোট উপাদান বের করুন।
• একই ফাংশন রিভার্সড অ্যারে-র ওপর প্রয়োগ করে ডান ছোট উপাদান বের করুন।
• সর্বোচ্চ |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[-1] >= A[i]:
            stack.pop()
        if stack:
            temp[i] = 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