C++ में विषम सम कूद

मान लीजिए हमारे पास एक सरणी A है। कुछ प्रारंभिक इंडेक्स से, हम कूद की एक श्रृंखला बना सकते हैं। श्रृंखला में स्थिति (1, 3, 5, ...) को विषम संख्या वाली कूद कहा जाता है, और स्थिति (2, 4, 6, ...) को सम संख्या वाली कूद कहा जाता है।

अब हम इंडेक्स i से आगे इंडेक्स j (i < j के साथ) पर इस तरह कूद सकते हैं:

विषम संख्या वाली कूद के दौरान, हम इंडेक्स j पर कूद सकते हैं जैसे कि A[i] <= A[j] और A[j] सबसे छोटा संभव मान हो। जब ऐसे कई इंडेक्स j हों, तो हम केवल सबसे छोटे ऐसे इंडेक्स j पर कूद सकते हैं।
सम संख्या वाली कूद के दौरान, हम इंडेक्स j पर कूद सकते हैं जैसे कि A[i] >= A[j] और A[j] सबसे बड़ा संभव मान हो। जब ऐसे कई इंडेक्स j हों, तो हम केवल सबसे छोटे ऐसे इंडेक्स j पर कूद सकते हैं।
यह मामला हो सकता है कि कुछ इंडेक्स i के लिए, कोई कानूनी कूद न हो।

अब एक प्रारंभिक इंडेक्स को अच्छा कहा जाता है जब, उस इंडेक्स से शुरू करके, हम कुछ बार कूदकर सरणी के अंत तक पहुंच सकते हैं।

हमें अच्छे प्रारंभिक इंडेक्स की संख्या ज्ञात करनी है।

यदि इनपुट [10,13,12,14,15] है, तो आउटपुट 2 होगा, क्योंकि दो स्थान इंडेक्स 3 और 4 हैं जहां से हम अंत तक पहुंच सकते हैं।

हल करने के चरण

ret := 1, n := A का आकार
nextGreaterEqual और nextSmallerEqual सरणी को -1 से भरें
एक मैप st परिभाषित करें
n-1 से 0 तक पीछे की ओर: lower_bound का उपयोग करके nextGreaterEqual और nextSmallerEqual की गणना करें, st[A[i]] = i
आकार n x 2 का 2D सरणी v परिभाषित करें और false से भरें
v[n-1][0] = v[n-1][1] = true
n-2 से 0 तक: v[i][1] = v[nextGreaterEqual[i]][0], v[i][0] = v[nextSmallerEqual[i]][1], यदि v[i][1] तो ret++
ret लौटाएं

उदाहरण

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

class Solution { 
public: 
    int oddEvenJumps(vector<int>& A) { 
        int ret = 1; 
        int n = A.size(); 
        vector<int> nextGreaterEqual(n, -1); 
        vector<int> nextSmallerEqual(n, -1); 
        map<int, int> st; 
        for (int i = n - 1; i >= 0; i--) { 
            map<int, int>::iterator it = st.lower_bound(A[i]); 
            nextGreaterEqual[i] = (it != st.end()) ? it->second : -1; 
            if (it != st.end() && it->first == A[i]) it++; 
            nextSmallerEqual[i] = it != st.begin() ? prev(it)->second : -1; 
            st[A[i]] = i; 
        } 
        vector<vector<bool> > v(n, vector<bool>(2, false)); 
        v[n - 1][0] = v[n - 1][1] = true; 
        for (int i = n - 2; i >= 0; i--) { 
            if (nextGreaterEqual[i] != -1) v[i][1] = v[nextGreaterEqual[i]][0]; 
            if (nextSmallerEqual[i] != -1) v[i][0] = v[nextSmallerEqual[i]][1]; 
            if (v[i][1]) ret++; 
        } 
        return ret; 
    } 
}; 

int main() { 
    Solution ob; 
    vector<int> v = {10,13,12,14,15}; 
    cout << (ob.oddEvenJumps(v)); 
    return 0; 
}

इनपुट

{10,13,12,14,15}