C++ में जांचें कि सरणी स्टैक-सॉर्टेबल है या नहीं

समस्या विवरण

मान लें हमारे पास nums नाम की एक सरणी है जिसमें 1 से n तक के अद्वितीय तत्व हैं। हमें जांचना है कि यह स्टैक-सॉर्टेबल है या नहीं। एक सरणी स्टैक-सॉर्टेबल होती है जब इसे अस्थायी स्टैक का उपयोग करके किसी अन्य सरणी में संग्रहीत किया जा सकता है।

इसे हल करने के लिए, हम सरणी पर इनमें से किसी भी ऑपरेशन का उपयोग कर सकते हैं:

सरणी के प्रारंभिक तत्व को हटाएं और उस आइटम को स्टैक में डालें।
स्टैक के शीर्ष तत्व को हटाएं और इसे दूसरी सरणी के अंत में डालें।
अब यदि दिए गए सरणी के सभी तत्व इन ऑपरेशनों द्वारा दूसरी सरणी में स्थानांतरित हो जाते हैं ताकि दूसरी सरणी गैर-घटते क्रम में सॉर्ट हो जाए, तो दी गई सरणी स्टैक-सॉर्टेबल है।

इसलिए, यदि इनपुट nums = [8, 6, 5, 3, 1] जैसा है, तो आउटपुट True होगा क्योंकि हम घड़ी की दिशा में दो बार घुमा सकते हैं तो यह सॉर्ट हो जाएगा जैसे [1, 3, 4, 5, 6, 8]

हल करने के चरण

एक स्टैक stk परिभाषित करें
last := 0
i := 0 से प्रारंभ करें, जब i < v का आकार, अपडेट करें (i को 1 से बढ़ाएं), करें:
- यदि stk खाली नहीं है, तो:
  - top := stk का शीर्ष तत्व
  - जब top, (last + 1) के समान हो, करें:
    - last := last + 1
    - stk से पॉप करें
    - यदि stk खाली है, तो:
      - लूप से बाहर आएं
    - top := stk का शीर्ष तत्व
  - यदि stk खाली है, तो:
    - v[i] को stk में डालें
  - अन्यथा:
    - top := stk का शीर्ष तत्व
    - यदि v[i] < top, तो:
      - v[i] को stk में डालें
    - अन्यथा:
      - false लौटाएं
- अन्यथा:
  - v[i] को stk में डालें
true लौटाएं

C++ कोड उदाहरण

#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}