C++-এ একটি অ্যারে স্ট্যাক-সর্টেবল কিনা চেক করা

মান লইয়া, আমাদের একটি অ্যারে nums আছে যাতে ১ থেকে n পর্যন্ত ইউনিক এলিমেন্ট আছে। আমাদের চেক করতে হবে এটি স্ট্যাক-সর্টেবল কিনা। একটি অ্যারে স্ট্যাক-সর্টেবল হয় যখন সেটি একটি টেম্পোরারি স্ট্যাক ব্যবহার করে অন্য একটি অ্যারেতে সংরক্ষণ করা যায়।

এটি সমাধান করার জন্য অ্যারেতে নিচের অপারেশনগুলো ব্যবহার করা যায়:

অ্যারেতি শুরুয় এলিমেন্টটি ডিলিট করে সেটি স্টকে পুশ করুন।
স্টকের টপ এলিমেন্ট ডিলিট করে সেকেন্ড অ্যারেতে শেষে ইনসার্ট করুন।

এখন যদি দেয়া অ্যারেতে থাকা সকল এলিমেন্ট এই অপারেশনগুলো দিয়ে সেকেন্ড অ্যারেতে ট্রান্সফার করা যায় যাতে সেকেন্ড অ্যারেটি নন-ডিক্রিজিং অর্ডারে সর্টেড থাকে, তবে দেয়া অ্যারেটি স্ট্যাক-সর্টেবল।

তাহলে, যদি ইনপুট হয় nums = [8, 6, 5, 3, 1], তবে আউটপুট হবে True কারণ আমরা দুবার ক্লকওয়াইজ ঘুরিয়ে সেটিকে সর্টেড করতে পারি [1, 3, 4, 5, 6, 8] আকারে।

এটি সমাধান করার জন্য নিচের ধাপগুলো অনুসরণ করব:

একটি স্ট্যাক stk সংজ্ঞায়িত করুন
last := 0
i := 0 থেকে v-এর সাইজ পর্যন্ত লুপ চালান, 거기서
- যদি stk খালি না হয়, তবে
  - top := stk-এর টপ এলিমেন্ট
  - while top == (last + 1) হলে
    - last := last + 1
    - stk-এ থেকে পপ করুন
    - যদি stk খালি হয়, তবে:
      - লুপ থেকে বের হয়ে যান
    - top := stk-এর টপ এলিমেন্ট
  - যদি stk খালি হয়, তবে:
    - v[i] স্টকে পুশ করুন
  - অন্যথায়
    - top := stk-এর টপ এলিমেন্ট
    - যদি v[i] < top হয়, তবে:
      - v[i] স্টকে পুশ করুন
    - অন্যথায়
      - false রিটার্ন করুন
- অন্যথায়
  - v[i] স্টকে পুশ করুন
true রিটার্ন করুন

উদাহরণ কোড

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

bool solve(vector<int> &v) {
    stack<int> stk; 
    int last = 0; 
    
    for (int i = 0; i < v.size(); i++) {
        if (!stk.empty()) {
            int top = stk.top(); 
            while (top == last + 1) {
                last = last + 1; 
                stk.pop(); 
                if (stk.empty()) {
                    break; 
                } 
                top = stk.top(); 
            } 
            
            if (stk.empty()) {
                stk.push(v[i]); 
            } else {
                top = stk.top(); 
                if (v[i] < top) {
                    stk.push(v[i]); 
                } else {
                    return false; 
                } 
            } 
        } else {
            stk.push(v[i]); 
        } 
    } 
    
    return true; 
} 

int main() { 
    vector<int> v = {8, 6, 5, 3, 1}; 
    cout << solve(v); 
}

ইনপুট

{8, 6, 5, 3, 1}