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

কনসেপ্ট

একটি পূর্ণসংখ্যার অ্যারে দেওয়া আছে। প্রতিটি উপাদানের নিকটতম বাম ছোট উপাদান (LS) এবং ডান ছোট উপাদান (RS) এর মধ্যে পরম পার্থক্যের সর্বোচ্চ মান খুঁজে বের করুন। যদি কোনো পাশে ছোট উপাদান না থাকে তবে ০ ধরা হয়।

ইনপুট ১

arr[] = {3, 2, 9}

আউটপুট ১

2

LS[] = {0, 0, 2}, RS[] = {2, 0, 0}, সর্বোচ্চ পার্থক্য = |2-0| = 2

ইনপুট ২

arr[] = {3, 5, 9, 8, 8, 10, 4}

আউটপুট ২

4

LS[] = {0, 3, 5, 5, 5, 8, 3}, RS[] = {0, 4, 8, 4, 4, 4, 0}, সর্বোচ্চ পার্থক্য = |8-4| = 4

পদ্ধতি

O(n²) সহজ সমাধান: প্রতিটি উপাদানের জন্য বাম ও ডান ছোট উপাদান খুঁজে বের করুন।

O(n) দক্ষ সমাধান: স্ট্যাক (Stack) ব্যবহার করুন। একই ফাংশন দিয়ে বাম ও ডান ছোট উপাদান দুটোই খুঁজে বের করা যায়।

1. বাম ছোট উপাদান (LS[]): খালি স্ট্যাক S। প্রতিটি Array[i]-এর জন্য S-র টপ >= Array[i] হলে পপ করুন। S খালি হলে LS[i]=0, নয়লে LS[i]=S.top()। Array[i] পুশ করুন।
2. ডান ছোট উপাদান (RS[]): অ্যারে রিভার্স করুন। একই প্রক্রিয়া দিয়ে RRS[] পূরণ করুন। রিভার্সড অ্যারেতে RS[i] = RRS[n-i-1]।
3. সর্বোচ্চ |LS[i] - RS[n-i-1]| গণনা করুন।

উদাহরণ (C++ কোড)

// C++ প্রোগ্রাম: বাম ও ডান ছোট উপাদানের পার্থক্য
#include <bits/stdc++.h>
using namespace std;

// বাম ছোট উপাদান পূরণের ফাংশন
void leftSmaller(int Array[], int n1, int SE1[]) {
    stack S1;
    for (int i = 0; i < n1; i++) {
        while (!S1.empty() && S1.top() >= Array[i])
            S1.pop();
        if (!S1.empty()) SE1[i] = S1.top();
        else SE1[i] = 0;
        S1.push(Array[i]);
    }
}

// সর্বোচ্চ পার্থক্য ফেরত দেওয়ার ফাংশন
int findMaxDiff(int Array[], int n1) {
    int LS1[n1];
    leftSmaller(Array, n1, LS1);
    int RRS1[n1];
    reverse(Array, Array + n1);
    leftSmaller(Array, n1, RRS1);
    int result1 = -1;
    for (int i = 0; i < n1; i++)
        result1 = max(result1, abs(LS1[i] - RRS1[n1-1-i]));
    return result1;
}

int main() {
    int Array[] = {3, 5, 9, 8, 8, 10, 4};
    int n = sizeof(Array) / sizeof(Array[0]);
    cout << "সর্বোচ্চ পার্থক্য: " << findMaxDiff(Array, n) << endl;
    return 0;
}

আউটপুট

সর্বোচ্চ পার্থক্য: 4