সি++-এ অ্যারেতে পরবর্তী ছোট উপাদান (Next Smaller Element) বের করা

একটি অ্যারেতে প্রতিটি উপাদানের জন্য তার ডানপাশে থাকা প্রথম ছোট উপাদানটি বের করতে হবে। না থাকলে -১।

উদাহরণ

অ্যারে: [5, 4, 3, 2, 1]

আউটপুট:

1 -> 2
2 -> 3
3 -> 4
4 -> 5
5 -> -1

অ্যালগরিদম (স্ট্যাক ব্যবহার)

স্ট্যাক ইনিশিয়ালাইজ করুন।
প্রথম উপাদান স্টকে পুশ করুন।
বাকি উপাদানগুলো জন্য লুপ:
স্ট্যাক খালি হলে পুশ করুন।
যখন বর্তমান উপাদান স্ট্যাকের টপ চেয়ে ছোট, টপ পপ করুন এবং আউটপুট দিন।
বর্তমান উপাদান পুশ করুন।
শেষে স্ট্যাকে থাকা উপাদানগুলোর জন্য -১ প্রিন্ট করুন।

সি++ ইমপ্লিমেন্টেশন

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

void nextSmallerElements(int arr[], int n) {
    stack s;
    s.push(arr[0]);
    for (int i = 1; i < n; i++) {
        if (s.empty()) { s.push(arr[i]); continue; }
        while (!s.empty() && s.top() > arr[i]) {
            cout << s.top() << " -> " << arr[i] << endl;
            s.pop();
        }
        s.push(arr[i]);
    }
    while (!s.empty()) {
        cout << s.top() << " -> -1" << endl;
        s.pop();
    }
}

int main() {
    int arr[] = {5, 4, 3, 2, 1};
    int n = 5;
    nextSmallerElements(arr, n);
    return 0;
}

আউটপুট

1 -> 2
2 -> 3
3 -> 4
4 -> 5
5 -> -1