C++-এ অ্যারেতে পূর্ববর্তী সর্বোচ্চ উপাদান (Previous Greater Element)

এই সমস্যাতে, একটি অ্যারে দেওয়া থাকে। প্রতিটি উপাদানের জন্য তার পূর্ববর্তী (left side) সর্বোচ্চ উপাদান বের করতে হবে। যদি নাই তবে -1 প্রিন্ট করুন।

উদাহরণ

ইনপুট: {6, 2, 7, 1, 5, 3}

আউটপুট: -1, 6, -1, 7, 7, 7

পদ্ধতি ১: নেস্টেড লুপ (O(n²))

প্রতিটি উপাদানের জন্য তার বাম পাশে লুপ চালিয়ে প্রথম বড় উপাদান খুঁজুন।

পদ্ধতি ২: স্ট্যাক ব্যবহার (O(n)) - কার্যকর

স্ট্যাকে মোনোটোনিক ডিক্রিজিং অর্ডার মেইনটেইন করুন। নতুন উপাদান আসলে ছোট উপাদানগুলো পপ করুন। স্ট্যাকে টপই হবে প্রিভিয়াস গ্রেটার।

C++ প্রোগ্রাম উদাহরণ (স্ট্যাক পদ্ধতি)

#include <bits/stdc++.h>
using namespace std;

void precedingGreatestElement(int arr[], int n) {
    stack<int> elements;
    elements.push(arr[0]);
    cout << "-1\t";
    
    for (int i = 1; i < n; i++) {
        while (!elements.empty() && elements.top() < arr[i])
            elements.pop();
        
        if (elements.empty())
            cout << "-1\t";
        else
            cout << elements.top() << "\t";
        
        elements.push(arr[i]);
    }
}

int main() {
    int arr[] = {6, 2, 7, 1, 12, 5};
    int n = sizeof(arr) / sizeof(arr[0]);
    precedingGreatestElement(arr, n);
    return 0;
}

আউটপুট

-1  6  -1  7  -1  12