C++ में वैश्विक और स्थानीय उलटफेर

मान लीजिए हमारे पास [0, 1, ..., N - 1] का कुछ क्रमपरिवर्तन A है, जहां N, A की लंबाई है। अब (वैश्विक) उलटफेर की संख्या i < j की संख्या है जहां 0 <= i < j < N और A[i] > A[j]। और स्थानीय उलटफेर की संख्या i की संख्या है जहां 0 <= i < N और A[i] > A[i+1]। हमें तभी true लौटाना है जब वैश्विक उलटफेर की संख्या स्थानीय उलटफेर की संख्या के बराबर हो। तो यदि इनपुट [1,0,2] जैसा है, तो true लौटाएं, क्योंकि केवल एक स्थानीय उलटफेर और एक वैश्विक उलटफेर है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• maxVal := -1, n := A का आकार
• i को 0 से n - 3 की रेंज में
  • maxVal := A[i] और maxVal का अधिकतम
  • यदि maxVal > A[i + 2], तो false लौटाएं
• true लौटाएं

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

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

class Solution {
public:
    bool isIdealPermutation(vector<int>& A) {
        int maxVal = -1;
        int n = A.size();
        for(int i = 0; i < n - 2; i++){
            maxVal = max(A[i], maxVal);
            if(maxVal > A[i + 2])
                return false;
        }
        return true;
    }
};

main(){
    vector<int> v = {1,0,2};
    Solution ob;
    cout << (ob.isIdealPermutation(v));
}

इनपुट

[1,0,2]

आउटपुट

1